Back to solutions

Remove Nth Node From End of List

MediumLinked List

Remove the n-th node from the end of a linked list and return its head, ideally in one pass.

Open problem
Constraints
  • 1 <= size <= 30
  • 1 <= n <= size

Two pointers with a gap

Time O(n)Space O(1)

Advance a lead pointer n steps ahead, then move both pointers until the lead reaches the end. The trailing pointer now sits just before the node to remove.

struct ListNode { int val; ListNode* next; };

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy{0, head};
    ListNode* fast = &dummy;
    ListNode* 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;
}