Remove Nth Node From End of List — Fast/Slow with Dummy

Problem 216 · Remove Nth Node From End of List

Difficulty: Medium · Pattern: Two Pointers (n-gap) + Dummy Head

Intuition

Advance fast pointer n+1 steps. Then move both until fast is null. Slow is now at the node before the target.

Solutions

# Python
def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n+1): fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

// Java
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head), fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;
    while (fast != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
}

// C++
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head), *fast = &dummy, *slow = &dummy;
    for (int i = 0; i <= n; i++) fast = fast->next;
    while (fast) { fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}

Complexity

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