The problem
Remove the n-th node from the end of a linked list and return the head.
Input: 1 → 2 → 3 → 4 → 5, n = 2 Output: 1 → 2 → 3 → 5
Picture it
Picture two inspectors walking along the train. The front inspector starts n coaches ahead. Then both walk at the same pace. When the front inspector steps off the end, the back inspector is standing right before the coach to remove, so they simply uncouple it. A dummy coach at the start handles removing the very first coach.
How to recognise it
- You need a node counted from the end of a singly linked list, but you can only walk from the front.
- "n-th from the end" means "the node whose distance to the end is n". Two pointers kept exactly n apart turn that distance into something you can walk.
- Removing a node means changing the
nextof the node before it, so you want to stop one step early. - The node to remove may be the head, which has no node before it. That calls for a dummy node: a placeholder placed in front of the head.
- The follow-up asks for one pass.
Start with brute force
Walk once to count the length L. The node to remove is at position L − n from the front (0-based), so walk again to the node just before it and skip over the target.
def remove_nth_brute(head, n):
length, node = 0, head
while node:
length += 1
node = node.next
dummy = Node(0, head)
before = dummy
for _ in range(length - n):
before = before.next
before.next = before.next.next
return dummy.next
Time is O(L) and space O(1). LeetCode allows at most 30 nodes, so this is not slow at all. The only drawback is that it reads the list twice, and the follow-up asks for a single pass. That matters when walking a node is expensive or the list arrives as a stream you cannot rewind.
From brute force to the idea
- Find the waste. The first pass exists only to learn L, so that you know when you are n steps from the end. A second pointer can tell you that instead.
- Open a gap. Start
fastandslowat the dummy. Movefastforward n + 1 steps. Now there are exactly n nodes strictly betweenslowandfast. - Move together. Step both until
fastisNone(it has gone past the last node). The gap has not changed, soslowis now the node just before the n-th from the end. That is why the gap is n + 1, not n. - Skip the target.
slow.next = slow.next.nextunhooks it. - Return
dummy.next. If the head was removed,slowstayed at the dummy, anddummy.nextis now the second node. No special case is needed.
This is the key idea: keep two pointers a fixed distance apart, so when the leader reaches the end, the follower is where you need to act.
The key idea
Keep a gap of n between two pointers; when the leader reaches the end, the follower is just before the target. One pass.
Python solution
def remove_nth(head, n):
dummy = Node(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast, slow = fast.next, slow.next
slow.next = slow.next.next
return dummy.nextIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(L): one pass to count, one to reach the node | O(1): a counter and two references |
| Two pointers (shown code) | O(L): fast walks the list once and slow follows | O(1): the dummy node and two references |
Both are O(L). The gain is one pass instead of two, not a better big-O.
Edge cases
- Remove the head (
1 → 2, n = 2):fastreachesNonestraight away,slowstays at the dummy, and the result is2. - Single node (
1, n = 1): the result is an empty list (None). - Remove the last node (
1 → 2 → 3, n = 1):slowstops at 2 and the result is1 → 2. - n larger than the length: LeetCode guarantees 1 ≤ n ≤ L. With n = L + 1 the first loop steps past
Noneand the shown code raisesAttributeError. - Node class: the shown code builds the dummy with
Node(0, head), so the class must accept a value and a next node. On LeetCode it is calledListNode.
Common mistakes
- Moving
fastonly n steps.slowthen stops on the target instead of before it, and the code removes the node after it. - Starting at
headinstead of a dummy, which makes removing the head a special case (and a crash if you forget it). - Returning
headinstead ofdummy.next. When the head was removed,headstill points at the removed node.
Delete the middle node of a list of length L, which is node ⌊L / 2⌋ counting from 0. For 1 → 2 → 3 → 4 that is node 3, giving 1 → 2 → 4; a single node gives an empty list. Use one pass. Describe your approach, then write it if you like.
Compare with our answer
Two pointers again, but with different speeds instead of a fixed gap. fast moves two steps for each step of slow, so when fast reaches the end, slow has gone half as far. Start slow at a dummy so it stops just before the middle.
def delete_middle(head):
dummy = Node(0, head)
slow, fast = dummy, head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
slow.next = slow.next.next
return dummy.next
Time O(L), space O(1).
A strong answer mentions: fast and slow speeds instead of a gap, starting slow one step behind (at the dummy) so it lands before the middle, and checking lengths 1, 2 and 3 by hand.
1. A long linked list must not be modified, and you may walk it only once. You need the value k-th from the end. Which approach fits best?
A fixed gap of k gives the answer when the leader reaches the end: one pass, O(1) space, no changes. Reversing modifies and rereads the list, recursion uses O(L) stack, and counting is two passes.
2. What problem does the dummy node solve in the shown code?
To remove a node you change the next of the node before it. The head has no such node, so the dummy provides one. It does not guard against an invalid n: that still raises an error.
3. A learner writes for _ in range(n) instead of range(n + 1). What is returned for 1 → 2 → 3 → 4 → 5 with n = 2?
With a gap of n, slow stops on node 4 (the target) instead of before it, so slow.next = slow.next.next removes node 5.
Score 60% or more and the lesson is marked complete.