~20 minutes · Day 25 · gap pointers · Python
Tonight's linked-list problem is Remove Nth Node From End of List. Interviewers like it because the target is described from the end, but a singly linked list only lets you move forward (Wikipedia: linked list). The win is learning how to turn “n from the end” into a fixed gap between two pointers.
Lead one pointer n steps ahead, then walk both together; when the leader hits the end, the trailer sits at the target.
That sentence is the pattern. The leader discovers the end. The trailer keeps exactly the same distance behind it. When the leader has no more list to walk, the trailer is forced to be exactly n nodes from the end.
After the first loop, fast is exactly n nodes ahead; moving both pointers preserves that gap.
The brute-force version stores every node in an array, then indexes backward to find the node before the one to remove. It is O(n) time and O(n) space (Big O notation):
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
nodes = [dummy]
cur = head
while cur:
nodes.append(cur)
cur = cur.next
prev = nodes[len(nodes) - n - 1]
prev.next = prev.next.next
return dummy.next
This works, but the array is the crutch. The interview version asks you to keep O(1) extra space and still remove the right node in one forward walk.
First move fast exactly n steps ahead of slow. Then move both until fast falls off the end. At that moment, slow is the node to remove. A dummy node and prev pointer make deleting the real head the same as deleting any other node; the LeetCode statement guarantees n is valid (LeetCode: Remove Nth Node From End of List).
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast, slow = head, head
prev = dummy
for _ in range(n):
fast = fast.next # create an n-node gap
while fast:
fast = fast.next # preserve the gap
prev = slow # prev trails the target
slow = slow.next # slow moves toward target
prev.next = slow.next # remove slow
return dummy.next # real head may have changed
Trace 1 -> 2 -> 3 -> 4 -> 5 with n = 2. After the first loop, fast is at 3 and slow is at 1. They walk together until fast becomes None; now slow is at 4, the node to remove, and prev is at 3.
At the end of the walk, slow is the target and prev is the node whose next arrow must skip it.
New problem shape: return the nth node from the end of a linked list. No deletion, only find the node.
Before opening the reveal: which pointer disappears from the code, and why? Say the invariant out loud first.
You no longer need prev, because there is no arrow to reconnect. Keep only the leader and trailer:
def nth_from_end(head, n):
leader = trailer = head
for _ in range(n):
leader = leader.next
while leader:
leader = leader.next
trailer = trailer.next
return trailer
Same skeleton. The deletion problem adds prev only because removing a node means changing the previous node's next arrow.
| Approach | Time | Space |
|---|---|---|
| Brute force node array | O(n) | O(n) |
| Gap pointers | O(n) | O(1) |
The speed is still linear. The pattern buys the interview version: one forward pass, constant extra memory, and no indexing into a list that cannot index.
1. What creates the gap?
n.2. In the find-only version, when leader reaches the end, where is trailer?
n nodes behind the leader. When the leader is at the end, the trailer is exactly n from the end.3. Spot the bug in this removal:
fast, slow = head, head
for _ in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.nextslow is the target node. To remove it, you need the previous node, not slow itself.4. Which task is this pattern?
Solve Remove Nth Node From End of List in your Notion tracker with the cycle — predict → attempt → compare → encode.
1 -> 2 -> 3 -> 4 -> 5, choose n = 2, and state the invariant.Watch NeetCode — Remove Nth Node From End of List after your attempt, as the compare step. Listen for how he keeps the gap fixed before deleting the node.