DSA sheet · Linked List · Fast & slow pointer pattern

Remove Nth Node from End of List

This is the fourth fast and slow pointer problem, and it teaches something new about the pattern: "fast" doesn't have to mean "double speed". It can mean "starts ahead". The teacher first solves it in two passes: count the length, then walk to the right spot. Then she uses a picture from athletics, the staggered start on an oval track, to do it in one pass with a fixed gap between two pointers. Along the way she shows why a dummy node saves us from messy special cases when the head itself has to be deleted.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: count the length, then walk (two passes)
• Part B · Optimal: a gap of n + 1 between two pointers, with a dummy node (one pass)
• Part C · Revision page

Part 0 · Before starting

Linked list basics

A linked list is a chain of nodes. Each node stores a val and a pointer next to the following node. The last node's next is None. We are handed only the first node, the head.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

[1] → [2] → [3] → [4] → [5] → None
 ↑
head

• Walking: curr = head, then curr = curr.next until curr is None. Every curr = curr.next is called one jump on this page.
• No index access: you can't say "give me node number 4". You must jump from the head, so reaching position i costs O(n). And there is no way to walk backwards, so "the 2nd node from the end" can't be reached directly.
• Keep head safe: walk with a copy like curr; head itself must stay on the first node so we can return it.
• Save next before changing a pointer: when you rewire node.next, whatever it pointed to before is lost unless something else still points to it.

How to delete a node (recap)

To delete a node you must stand on the node just before it. Then you make that node skip over it:

before:  [1] → [2] → [3] → [4] → [5] → None
                      ↑
                     prev        (we want to delete 4)

prev.next = prev.next.next

after:   [1] → [2] → [3] ──────→ [5] → None        (4 is cut out)

prev.next is node 4. prev.next.next is what 4 points to, node 5. So 3 now points straight to 5. Nothing points to 4 any more, so it's gone from the list. If 4 were the last node, prev.next.next would be None, and 3 would become the new last node. Works the same.

The dummy node

A dummy is a fake extra node we put in front of head: dummy = ListNode(0), dummy.next = head.

[0] → [1] → [2] → [3] → [4] → [5] → None
 ↑     ↑
dummy head

Why? Deleting needs a node before the target. Every real node has one, except head. The dummy gives head a "previous node" too, so deleting head works with the exact same line as deleting any other node. No special if. At the end we return dummy.next, which is the real (possibly new) head.

The two-pointer gap

In the earlier fast and slow problems, fast moved 2 steps and slow moved 1. Here both move 1 step at a time, but fast starts some steps ahead. Because they move at the same speed, the gap between them never changes. When fast reaches the end, slow is exactly "gap" nodes behind the end. That's how we measure a distance from the end without knowing the length.

Part A · Brute force: count the length, then walk (two passes)

LeetCode 19

1The question in simple words

You get the head of a linked list and a number n. Remove the n-th node counting from the end (n = 1 means the last node, n = 2 the second-last, and so on). Return the head of the changed list.

[1] → [2] → [3] → [4] → [5] → None
                   2nd   1st   (from end)
result: [1] → [2] → [3] → [5] → None

[1] → None
result: None

2What the constraints tell us

• Number of nodes: 1 to 30 → the list is never empty. But it can be a single node, and removing it leaves an empty list (return None).
• 1 ≤ n ≤ length → n is always valid. When n = length, the node to remove is the head. That's the tricky case.
• 30 nodes is tiny. TLE starts somewhere around 10⁸ (sometimes up to 5·10⁸) simple operations, so time is no worry at all. The teacher still wants the cleanest, fastest version, because that's what the interviewer is checking.

3Intuition: turn "from the end" into "from the start"

We can't walk backwards. But if we know the total length L, then "n-th from the end" is the same node as "(L − n + 1)-th from the start". And to delete it, we need to stand on the node before it. So: count the length first, then walk to the node just before the target.

4Building the logic from examples

How many jumps from head to the node before the target?

The teacher guesses and tests a formula on examples, which is a good habit.

• Guess 1: n jumps? List 1 → 2 → 3 → 4 → 5, n = 2: we must stand on 3, which is 2 jumps from head (1 → 2 → 3). It matches! But try a 7-node list 1 … 7 with n = 2: the target is 6, so we stand on 5. That's 4 jumps, not 2. Guess 1 fails.
• Guess 2: L − n jumps? 7 − 2 = 5, but we needed 4. One too many.
• Guess 3: L − n − 1 jumps. Check: 7 nodes, n = 2 → 7 − 2 − 1 = 4 ✓. 5 nodes, n = 2 → 5 − 2 − 1 = 2 ✓. 7 nodes, n = 5 → the target is node 3, so stand on node 2 → 7 − 5 − 1 = 1 jump ✓.

Counting the length, and why the starting value matters

Walk with curr from head and add 1 for each node until curr is None. The teacher warns: be careful what your counter actually counts.

• Count nodes (start at 0, add 1 each time you stand on a node): you get L = 5 for the 5-node list. Then the jump formula is L − n − 1.
• Count jumps (stop when curr.next is None): you get 4 for the same list, already one less. Then the formula becomes "count − n".

Both are fine. What's not fine is mixing them: one counting style with the other style's formula. Pick one and stay consistent. On this page we count nodes, so L is the real length.

The head case: n = L

If n equals the length, the target is the head itself. Then L − n − 1 = −1: there's no node before it. So handle it first: if n == L, return head.next. The second node becomes the new head (or None if there was only one node).

The delete step

After the jumps, curr is on the node before the target. curr.next = curr.next.next. In the teacher's example of removing the last node (n = 1) from 1 … 5, we stand on 4. 4's next is 5, and 5's next is None, so 4's next becomes None and 5 is gone.

5Approach steps

1. Count the nodes: L.
2. If n == L → the head must go → return head.next.
3. Otherwise put curr back at head and jump L − n − 1 times.
4. curr.next = curr.next.next.
5. Return head (it didn't change).

6Code (Python)

class Solution:
    def removeNthFromEnd(self, head, n):
        length = 0
        curr = head
        while curr is not None:          # pass 1: count the nodes
            length += 1
            curr = curr.next

        if n == length:                  # the head itself must go
            return head.next

        curr = head
        for _ in range(length - n - 1):  # pass 2: stand before the target
            curr = curr.next
        curr.next = curr.next.next       # skip over the target
        return head

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5, n = 2.

after the jumps:
[1] → [2] → [3] → [4] → [5] → None
             ↑
            curr

after curr.next = curr.next.next:
[1] → [2] → [3] ──────→ [5] → None

Head case: 1 → 2, n = 2 → length 2 = n → return node 2. Result: 2 → None ✓. One node, n = 1 → return head.next = None ✓.

9Complexity & remember

• Time O(2n) = O(n): one full pass to count, then up to another pass to walk. The teacher notes that in linked lists, "2n" or "3n" is typical for a brute force; the optimisation is to bring it down to one pass.
• Space O(1): only a counter and a pointer.

Part B · Optimal: a gap of n + 1 between two pointers, with a dummy node (one pass)

1The question (same as Part A)

Same input and output. New goal: only one pass over the list, no separate counting.

2What the constraints tell us

• n can equal the length, so the head can be the target. A dummy node will handle that without an if.
• One node and n = 1: the answer is an empty list. The dummy version returns dummy.next, which becomes None. No special case.

3Intuition: the staggered start on a running track

On an oval track, runners in the outer lanes start further ahead than runners in the inner lanes. Why? The outer lane is longer, so giving those runners a head start makes the race fair: everyone runs the same distance to the finish line.

Here we do the same thing on purpose. We give fast a head start of a fixed number of nodes, then move both pointers at the same speed. The gap stays constant. When fast crosses the finish line (None), slow is exactly that gap behind the end.

4Building the logic from examples

How big should the gap be? n + 1 jumps

We want slow to finish on the node before the target, because that's where deleting happens. The target is n nodes from the end; the node before it is n + 1 nodes from the end. So fast should be n + 1 jumps ahead of slow.

Teacher's first example, without a dummy yet: 1 → 2 → 3 → 4 → 5, n = 2. Fast takes 3 jumps: 1 → 2 → 3 → 4. Slow stays on 1. Now both move 1 at a time:

• slow = 2, fast = 5
• slow = 3, fast = None → stop.

Slow is on 3, the node before 4 ✓. Delete with slow.next = slow.next.next.

Her bigger example: 1 → 2 → … → 8, n = 3 (target is 6). Fast takes 4 jumps to node 5; slow on 1. Then (2, 6), (3, 7), (4, 8), (5, None) → stop. Slow is on 5, one before 6 ✓.

The ugly case, and the dummy node

Now try one node [1] with n = 1. Fast needs 2 jumps from head, but after 1 jump it's already None, and the second jump would crash. You could patch it with checks like "if head.next is None and n == 1, return None", and also the general "target is head" case, but the teacher says that's a lot of messy if-else.

Instead: put a dummy node (value 0) in front of head, and start both slow and fast on the dummy.

[0] → [1] → None
 ↑
slow, fast (both on dummy)

• Fast takes n + 1 = 2 jumps: dummy → 1 → None. Fast is None.
• The "move both" loop doesn't run, since fast is already None. Slow stays on the dummy.
• slow.next = slow.next.next → dummy.next = 1.next = None. Node 1 is removed.
• Return dummy.next → None, the empty list ✓.

5Approach steps

1. Make dummy = ListNode(0), dummy.next = head.
2. Put slow and fast on the dummy.
3. Move fast n + 1 times.
4. While fast is not None: move both one step.
5. Now slow is just before the target: slow.next = slow.next.next.
6. Return dummy.next.

6Code (Python)

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)              # fake node before head
        dummy.next = head
        slow = dummy
        fast = dummy

        for _ in range(n + 1):           # head start: n + 1 jumps
            fast = fast.next

        while fast is not None:          # same speed until fast falls off
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next       # slow is just before the target
        return dummy.next                # the real head (may be new)

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5, n = 2. With the dummy: 0 → 1 → 2 → 3 → 4 → 5 → None.

after the head start (gap = 3):
[0] → [1] → [2] → [3] → [4] → [5] → None
 ↑                 ↑
slow              fast

when fast falls off:
[0] → [1] → [2] → [3] → [4] → [5] → None
                   ↑                  ↑
                  slow               fast

after slow.next = slow.next.next:
[0] → [1] → [2] → [3] ──────→ [5] → None
       ↑
  dummy.next (returned)

Removing the head: 1 → 2 → 3, n = 3

9Complexity & remember

• Time O(n), one pass. The teacher's argument: fast first takes n + 1 jumps, and then the while loop moves it from there to None. Together, fast walks the list from start to end exactly once (slow follows behind and never goes further than fast). So it's a single iteration, compared with the two passes of Part A.
• Space O(1): one dummy node and two pointers.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.removeNthFromEnd(build([1, 2, 3, 4, 5]), 2)))   # [1, 2, 3, 5]
print(to_list(s.removeNthFromEnd(build([1]), 1)))               # []
print(to_list(s.removeNthFromEnd(build([1, 2]), 1)))            # [1]
print(to_list(s.removeNthFromEnd(build([1, 2]), 2)))            # [2]
print(to_list(s.removeNthFromEnd(build(list(range(1, 9))), 3))) # [1, 2, 3, 4, 5, 7, 8]

Based on this video: Remove Nth Node From End of List | Fast and Slow Pointer