Remove the n-th node from the end

Delete a node counted from the back in a single pass, by keeping two references a fixed distance apart.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Move fast n nodes ahead, then move both together. When fast is on the last node, slow is sitting just before the node to delete.

Code

C++PythonC#

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

def remove_nth_from_end(head: ListNode, n: int) -> ListNode | None:
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n): fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

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

Tips

The dummy node (shown as D) makes removing the real head work without a special case.
Nothing is freed by hand. Once no reference points at the node, the garbage collector reclaims it.

In the .NET library

The object initialiser new ListNode(0) { next = head } creates the dummy and links it in one expression.