Question 19

Delete the Nth Node from the End of the Linked List

Given the head of a linked list, remove the Nth node from the end of the list and return its head.

Approach: Two-Pointer Technique

1. Initialize two pointers, first and second, both pointing to the head of the list.
2. Advance first pointer by N nodes. This creates a gap of N nodes between first and second.
3. Move both pointers until first reaches the end. Now, second will be pointing to the node just before the Nth node from the end.
4. Remove the target node by updating the next pointer of second.
5. Return the head of the modified list.

This approach allows us to make a single pass through the list.

Complexity

• Time Complexity: ( O(L) ), where ( L ) is the length of the list.
• Space Complexity: ( O(1) ), as we only use a constant amount of extra space.

Java Code Implementation

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;

    // Move first N+1 steps ahead
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }

    // Move both pointers until first reaches the end
    while (first != null) {
        first = first.next;
        second = second.next;
    }

    // Skip the target node
    second.next = second.next.next;

    return dummy.next;
}