Remove Nth Node From End of List

Medium#19n apart

You get the head of a linked list and a number n. Remove the n-th node counting from the end, where the last node is the 1st, and return the head of what is left. Our example: 7 → 3 → 8 → 2, n = 4 — the 4th from the end is the head 7, and the answer is 3 → 8 → 2.

19 Remove Nth Node From End of ListWalkthrough · 1×

Example: remove the 4th node from the end of 7 → 3 → 8 → 2: n is the whole length, so it is the head.

nonedummy7382head
slowfastremoved nodethe list returned

A dummy node in front of the head 7: now every node, the head too, has a node before it

01/14
restart · back · play · step
Speed
1function removeNthFromEnd(head, n):
2 dummy = new node whose next is head
3 fast = dummy
4 slow = dummy
5 repeat n times:
6 fast = fast.next
7 while fast.next is not none:
8 slow = slow.next
9 fast = fast.next
10 slow.next = slow.next.next
11 return dummy.next
state
slow
–
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. fast starts n nodes ahead and both then move one step at a time, so the gap stays n. When fast is on the last node, slow is n + 1 from the end: right before the node to remove.
  2. To remove a node you relink the node in front of it. The dummy gives even the head a node in front, so n equal to the length needs no special case: slow simply never leaves the dummy.
  3. For the same reason the answer is dummy.next, not head: when the head is removed, head still points at it.

Complexity

Time O(L), L the length of the list: fast walks it once, and slow walks behind it. Memory O(1): two pointers and one dummy node.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.