Remove Nth Node From End of List — Solution

Problem

Given the head of a singly linked list and an integer n, remove the nth node counting from the tail and return the modified list. The node you're removing is exactly n positions from the last node — so n=1 is the tail itself, n=2 is the one before it, and so on.

[1,2,3,4,5]

• Input: head = [1,2,3,4,5], n = 2
• Output: [1,2,3,5]
• Explanation: The 2nd node from the end is node 4; removing it connects node 3 directly to node 5.

Intuition

The hard part is finding a node's position from the end without knowing the list's total length. A two-pointer gap trick makes this work in a single pass: keep two pointers exactly n nodes apart, so that when the leading pointer exits the list, the trailing pointer lands on the node just before the one to delete.

Solution — Two Pointers (One Pass)

Use a dummy head node and two pointers separated by exactly n steps. When the fast pointer reaches the last node, the slow pointer is positioned right before the target node and can unlink it in constant time.

1. Create a dummy node pointing to head — this handles the edge case where the head itself is removed.
2. Set both slow and fast to dummy.
3. Advance fast exactly n steps forward to create the gap.
4. Move both pointers one step at a time until fast.next is null — fast is now at the last node.
5. Unlink the target: slow.next = slow.next.next.
6. Return dummy.next (not head, since head may have been removed).

1class Solution:
2    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
3        dummy = ListNode(0, head)  # sentinel lets us delete head without special-casing it
4        slow, fast = dummy, dummy
5
6        for _ in range(n):
7            fast = fast.next  # open a gap of exactly n nodes between slow and fast
8
9        while fast.next:               # stop when fast is at the last real node
10            slow = slow.next
11            fast = fast.next
12
13        slow.next = slow.next.next     # bypass the nth-from-end node
14        return dummy.next

Time: O(L) — one complete pass through a list of length L.
Space: O(1) — two extra pointers regardless of list size.

Complexity Summary

Common Mistakes

• Wrong stopping condition: Stopping when fast is null (not fast.next) puts slow one step too far — it ends up at the node to delete rather than just before it, so the unlink breaks.
• Moving fast n+1 times instead of n: Some versions check while fast != null instead of while fast.next != null; these require an extra initial step to stay correct. Mixing one version's gap size with the other's stopping condition deletes the wrong node.
• Returning head instead of dummy.next: When n equals the list's length, the head is the node to remove. Returning head gives back the deleted node; dummy.next always points to the correct new head.
• Omitting the dummy node for single-element lists: Without a sentinel, removing the only node requires a special if branch. The dummy node makes the pointer math uniform across all inputs.
• Forgetting that slow.next must exist when unlinking: The problem guarantees 1 ≤ n ≤ L, so slow.next is always valid at deletion time — but if you implement the gap incorrectly, you can reach a state where slow.next is null and the line crashes.

Related Problems

• middle-of-the-linked-list — same two-pointer gap concept used to find the midpoint in one pass
• palindrome-linked-list — combines two-pointer midpoint detection with in-place reversal
• reorder-list — uses two-pointer midpoint then merges the two halves in interleaved order
• odd-even-linked-list — rearranges all odd-indexed nodes before even-indexed ones by rewiring next pointers
• reverse-linked-list — foundational pointer manipulation that almost every linked list problem builds on