Remove Nth Node from end of list

19.Remove Nth Node From End of List

Linked List

Two Pointers

Problem Statement:

Given the head of a linked list, remove the nth node from the end of the list and return its head. Do it in one pass.

Example:

Input:

head = [1→2→3→4→5]
n = 2

→

Output:

[1→2→3→5]

The 2nd node from the end (4) is removed.

Algorithm:

1. Use two pointers: fast and slow
2. Move fast pointer n steps ahead
3. If fast is null, remove first node
4. Move both pointers until fast reaches end
5. Skip the nth node from end using slow pointer

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head, slow = head;
    
    // Move fast pointer n steps ahead
    while (n > 0) {
        fast = fast.next;
        n--;
    }
    
    // If fast is null, remove first node
    if (fast == null) return head.next;
    
    // Move both pointers until fast reaches end
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // Skip the nth node from end
    slow.next = slow.next.next;
    return head;   
}

Python Solution:

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    fast = slow = head
    
    # Move fast pointer ahead
    for _ in range(n):
        fast = fast.next
    
    # If fast is None, remove first node
    if not fast:
        return head.next
    
    # Move until fast reaches end
    while fast.next:
        fast = fast.next
        slow = slow.next
    
    # Remove nth node from end
    slow.next = slow.next.next
    return head

C++ Solution:

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *fast = head, *slow = head;
    
    // Move fast pointer ahead
    while (n--) {
        fast = fast->next;
    }
    
    // If fast is null, remove first node
    if (!fast) return head->next;
    
    // Move until fast reaches end
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // Remove nth node from end
    slow->next = slow->next->next;
    return head;
}