This is one of those linked list questions interviewers love because the brute-force answer is easy and the follow-up ("can you do it in one pass?") separates people who have actually practiced pointer gaps.
The problem
Given the head of a singly linked list, remove the n-th node from the end and return the head. Example: 1 -> 2 -> 3 -> 4 -> 5, n = 2 gives 1 -> 2 -> 3 -> 5.
Two passes (fine, but not the answer they want)
Count the length L, then walk L - n steps and unlink the next node. It is O(L) time and O(1) space, but it reads the list twice.
One pass: keep two pointers n nodes apart
- Put a dummy node in front of the head. This removes the special case where the head itself is deleted.
- Move
fastn steps ahead ofslow(both start at the dummy). - Move both together until
fast.nextis null. Nowslow.nextis the node to delete. slow.next = slow.next.next, returndummy.next.
def removeNthFromEnd(head, n):
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
Gotchas interviewers check
- Deleting the head (
n == L): without the dummy node you need anif. With it,slowstays on the dummy and the code just works. - Off-by-one in the gap: you want
slowto stop on the node before the target, so the loop condition isfast.next, notfast. - Single-node list:
[1], n = 1should return an empty list. Test it out loud.
Complexity
O(L) time, one traversal, O(1) extra space.
Practicing this pattern
The "gap of n" trick shows up again in middle-of-list, cycle detection and rotate-list problems, so say the invariant out loud: "fast is always n nodes ahead of slow." If you want a second pair of eyes during mock rounds, I work on Linkjob AI copilot, a real-time interview helper; disclosure: I'm on the team that builds it.