Remove Nth Node From End: Two Pointer Gap Technique

Remove Nth Node From End of List is LeetCode 19. It is a medium-difficulty problem, but the core idea is surprisingly clean once you see it. The trick is to use two pointers separated by a fixed gap so that when the leading pointer reaches the end, the trailing pointer is sitting right before the node you want to remove.

No second pass. No counting the length first. One traversal, done.

The problem

You are given the head of a linked list. Remove the nth node from the end of the list and return its head.

Example: given 1 -> 2 -> 3 -> 4 -> 5 and n = 2, remove the 2nd node from the end (node 4) and return 1 -> 2 -> 3 -> 5.

The brute force: two passes

The straightforward approach is to walk the list once to count its length, then walk it a second time to find the node at position length - n. Remove it, done.

def removeNthFromEnd(head, n):
    # First pass: count the length
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    # Edge case: remove the head itself
    if n == length:
        return head.next

    # Second pass: find the node before the target
    curr = head
    for _ in range(length - n - 1):
        curr = curr.next

    curr.next = curr.next.next
    return head

This works fine. O(n) time, O(1) space. But interviewers will almost always ask: "Can you do it in one pass?" That is where the two pointer gap technique comes in.

The gap technique: why it works

Here is the key insight. If you place two pointers n steps apart and then move them together at the same speed, when the front pointer reaches the end of the list, the back pointer will be exactly n steps from the end.

Think about it. If fast is at position k and slow is at position k - n, then when fast reaches the last node (position length - 1), slow is at position length - 1 - n. That puts slow right before the node we want to delete. One pointer reassignment and we are done.

The gap between the two pointers acts like a ruler. You are measuring n nodes from the end without ever knowing the total length. That is the elegance of this technique.

The dummy node trick

There is one wrinkle. What if we need to remove the head of the list? For example, 1 -> 2 with n = 2 means removing node 1 itself. If slow starts at the head, there is no "node before the target" to update.

The fix: add a dummy node before the head. Now slow starts at the dummy, and even if the target is the first real node, slow is sitting right before it. After the removal, return dummy.next instead of head.

Visual walkthrough

Let's trace through removing the 2nd node from the end of 1 -> 2 -> 3 -> 4 -> 5. Watch slow (amber) and fast (green) as they maintain a constant gap of 2.

The pattern is simple: create the gap, then walk in lockstep. When fast cannot move forward anymore, slow is parked right before the target. Skip the target node, and you are done.

The solution

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    slow = dummy
    fast = dummy

    # Phase 1: advance fast by n steps
    for _ in range(n):
        fast = fast.next

    # Phase 2: move both until fast reaches the last node
    while fast.next:
        slow = slow.next
        fast = fast.next

    # Delete the target node
    slow.next = slow.next.next

    return dummy.next

Let's break it down:

1. Dummy node. Creates a fake head so we never have to special-case removing the actual head.
2. Phase 1. Move fast forward by n steps. Now there is a gap of exactly n between slow and fast.
3. Phase 2. Move both pointers one step at a time. The gap stays constant. When fast.next is None, fast is at the last node.
4. Delete. slow.next is the node to remove. Skip it by pointing slow.next to slow.next.next.
5. Return. dummy.next is the head of the modified list.

Complexity analysis

Time: O(n). We traverse the list exactly once. Fast goes through all n nodes, and slow goes through most of them. Total work is proportional to the length of the list.

Space: O(1). Two pointer variables and one dummy node. No extra data structures.

Both approaches have the same big-O complexity. The one-pass version is not asymptotically faster, but it is cleaner and shows a deeper understanding of two pointer linked list techniques. That is what interviewers care about.

Edge cases

• Remove the head (n equals list length). The dummy node handles this. After the gap phase, slow is still at dummy. slow.next = slow.next.next skips the head. Return dummy.next.
• Single node list, n = 1. Remove the only node. slow stays at dummy, and slow.next.next is None. Return None. Correct.
• Remove the tail (n = 1). Fast advances 1 step. Then both walk until fast is at the last node. slow ends up at the second-to-last node. slow.next = None. The old tail is gone.
• n equals list length (remove first node again). Same as removing the head. The dummy node approach is consistent here.

The Building Blocks

This problem is built from one core building block:

Fast-slow pointer (gap technique). Two pointers that move through a linked list at the same speed but start at different positions. The fixed gap between them lets you locate a position relative to the end of the list without knowing its length. The leading pointer "measures" the distance to the end, and the trailing pointer stays exactly where you need it.

This building block shows up in several other problems:

• Linked List Cycle (LeetCode 141) uses two pointers at different speeds instead of different starting positions. Different flavor of the same fast-slow pointer idea.
• Middle of the Linked List (LeetCode 876) uses fast moving at 2x speed. When fast reaches the end, slow is at the middle. Same family of techniques.
• Rotate List (LeetCode 61) can be solved by finding the length, but you can also use a gap technique to find the new tail.
• Reorder List (LeetCode 143) uses fast-slow to find the midpoint before splitting and reversing the second half.
• Swap Nodes in Pairs (LeetCode 24) requires careful pointer manipulation in a linked list, where the dummy node trick is equally useful.

The gap technique and the dummy node trick are two tools that you will reach for constantly in linked list problems. Get comfortable with both.

Why you will forget this (and what to do about it)

The solution is short. That is part of the problem. There are just enough moving pieces (dummy node, gap creation, the fast.next condition, the final pointer skip) that getting one detail wrong breaks everything. Did you advance fast by n or n+1? Did you check fast or fast.next? Did you forget the dummy node and now your head-removal case is broken?

These are not conceptual mistakes. They are recall mistakes. The kind that only go away with repetition. Type the solution from memory a few times with increasing gaps between sessions, and the details lock in. You stop second-guessing whether the loop condition is fast or fast.next because your hands already know.

Related posts

• Reverse Linked List - The most fundamental linked list technique, testing your ability to manipulate pointers without losing your place
• Linked List Cycle - Another two pointer linked list problem where pointers at different speeds reveal structural information about the list