LeetCode 19 · Linked List

Remove Nth Node From End of List, explained with a picture

Two inspectors, n coaches apart.

MediumLinked List
▶ Watch it step by step

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 next of 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

  1. 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.
  2. Open a gap. Start fast and slow at the dummy. Move fast forward n + 1 steps. Now there are exactly n nodes strictly between slow and fast.
  3. Move together. Step both until fast is None (it has gone past the last node). The gap has not changed, so slow is now the node just before the n-th from the end. That is why the gap is n + 1, not n.
  4. Skip the target. slow.next = slow.next.next unhooks it.
  5. Return dummy.next. If the head was removed, slow stayed at the dummy, and dummy.next is 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.next

In 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

ApproachTimeSpace
Brute forceO(L): one pass to count, one to reach the nodeO(1): a counter and two references
Two pointers (shown code)O(L): fast walks the list once and slow followsO(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): fast reaches None straight away, slow stays at the dummy, and the result is 2.
  • Single node (1, n = 1): the result is an empty list (None).
  • Remove the last node (1 → 2 → 3, n = 1): slow stops at 2 and the result is 1 → 2.
  • n larger than the length: LeetCode guarantees 1 ≤ n ≤ L. With n = L + 1 the first loop steps past None and the shown code raises AttributeError.
  • 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 called ListNode.

Common mistakes

  • Moving fast only n steps. slow then stops on the target instead of before it, and the code removes the node after it.
  • Starting at head instead of a dummy, which makes removing the head a special case (and a crash if you forget it).
  • Returning head instead of dummy.next. When the head was removed, head still points at the removed node.
Your turn: delete the middle 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.

Check what stuck

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?

2. What problem does the dummy node solve in the shown code?

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?

Score 60% or more and the lesson is marked complete.