LeetCode & Algorithms Course
← Back to section

Pattern 1: Dummy node and two pointers

Two tools that show up in almost every list problem: the sentinel node (dummy), which removes the special case "what if it's the head?", and the two pointers with a fixed gap, which solve "from the end" in one pass.

🎯

Try it first: Remove Nth Node From End of List

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Remove the n-th node from the end of the list and return the head. Try to do it in a single pass.

Example: 1 → 2 → 3 → 4 → 5, n = 2 → removes the 4 → 1 → 2 → 3 → 5.

Carregando editor…

Did you try? The natural approach is to count the list size in one pass and, in another, walk to the right node — two passes, and still handle removing the head as a separate case. The theory below does it all in one pass and with no special case.

Theory 1: the dummy node (sentinel)

Operations on the head are annoying because the head has no "previous node" to relink. The result: a bunch of if head is None and if previous is None scattered around.

The dummy trick: create a fake node that points to the real head.

dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ ∅

Now every real node has a previous one (in the worst case, the dummy). You operate without special cases and, at the end, return dummy.next — which is the head (possibly a new one). Add one paper node, get branch-free code.

Theory 2: two pointers with a fixed gap

For questions like "the n-th from the end", you don't know where the end is without traversing. The insight: keep two pointers with a fixed gap of n nodes between them.

  1. Advance fast n steps ahead.
  2. Move fast and slow together until fast reaches the end.
  3. Since the distance between them is n, when fast runs out, slow is exactly n nodes before the end — right where you need it to relink.

One pass, without counting the size first. Combined with the dummy (for the case of removing the head), the code stays clean:

Carregando editor…

Why is it O(n) time and O(1) space?

Each pointer traverses the list once (fast walks n + the rest; slow walks the rest) — O(n) total, a single pass. We use only a few pointers, no auxiliary array → O(1) space. The "count and then walk" version is also O(n), but makes two passes and needs the special case for the head (which the dummy eliminates).

When to use each one

  • Dummy node: whenever the operation might touch the head (remove, insert at the start, merge). It costs one node and removes a bunch of ifs.
  • Two pointers with a gap: "n-th from the end", "remove the middle one", any "position relative to the end" in one pass.

🧠 Quick-check quiz

0/4

1. What is the dummy node (sentinel) for?

2. In 'n-th from the end', why does advancing fast n steps before moving both together solve it in one pass?

3. Why is the dummy especially useful in 'remove the n-th from the end'?

4. What is the complexity of remove-nth with two pointers + dummy?

Summary

  • Dummy node: a sentinel node before the head removes the special cases of operating at the start; return dummy.next.
  • Two pointers with a gap of n: solves "from the end" in one pass, without counting the size.
  • Together: O(n) time, O(1) space, no ugly branches.

Next lesson: the most classic pattern in this section — in-place reversal.

All lessons in this section