🔀

Two-Pointer Merge / Remove Nth

Fast pointer races ahead by n+1 steps to create an exact offset gap; then both move together until fast hits null — slow lands perfectly one step before the target node to snip it out. Merge pattern interleaves two sorted chains into one with a dummy-head sentinel.

Linked List Fast / Slow Pointer Offset Gap Dummy Head Time O(n) Space O(1)

📋 When to Use

Remove a node that is exactly n positions from the end — unknown length
Merge two or more sorted linked lists into one sorted list
Find the middle node in one pass (fast advances 2 at a time)
Detect where a cycle begins — fast/slow meet at entry
Need O(1) extra space — only a constant number of pointers

💡 The dummy head sentinel eliminates edge-case code for inserting at position 0. Always add it when building or modifying a list's head node.

⚡ Complexity

Time

O(n)

Space

O(1)

Remove Nth: single pass, O(L) where L = list length. Merge: O(n+m) where n, m are the two list lengths — each node visited exactly once.

🔑 Key Insight — Offset

gap(fast, slow) = n+1
⟹ when fast = null, slow = (n+1)th from end
⟹ slow.next is the target to remove

Problem Given 1→2→3→4→5, remove the 2nd node from the end (node 4). Use a dummy head and advance fast by n+1=3 steps so when fast reaches null, slow points just before the target node (LC #19). Tab 2 merges sorted lists 1→3→5 and 2→4→6 using a dummy head + tail pointer (LC #21).
Input (Tab 1): [1,2,3,4,5], n = 2 · Answer: [1,2,3,5] · Merge: [1,3,5] + [2,4,6] → [1,2,3,4,5,6]

Problem — LC #19 Remove Nth Node From End of List Given dummy→1→2→3→4→5, remove the 2nd node from the end (node 4). Use a dummy head + fast/slow offset of n+1 = 3 steps.

Step 1 / —

🚀 Advance Fast

🤝 Move Together

✂️ Remove Node

✅ Done

fast = races ahead 🐇

slow = lags behind 🐢

gap = n+1 between them

🔭 Gap (fast − slow):

🔵 fast → D

🟠 slow → D

📏 gap = 0

Click ▶ Play or Next ▶ to start the animation.

// Init: dummy node, fast=dummy, slow=dummy

Problem — LC #21 Merge Two Sorted Lists Merge 1→3→5 and 2→4→6 into one sorted list. Use a dummy head + tail pointer. Compare p1 vs p2 and append the smaller node each time.

Step 1 / —

🔍 Compare

➕ Append

✅ Done

p1 on list 1

p2 on list 2

tail = end of result so far

result list (building)

🔵 p1 → 1

🟣 p2 → 2

✅ result len = 0

Click ▶ Play or Next ▶ to start the animation.

// Init: dummy result, tail=dummy, p1→1, p2→2

☕ Java Pattern SkeletonsJAVA

✂️ Remove Nth From End — Offset Technique

// ── Remove Nth From End ──────────────────────────────────────────
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;

// advance fast n+1 steps ahead  (creates the magic gap)
for (int i = 0; i <= n; i++) fast = fast.next;

// move both until fast hits null
while (fast != null) {
    fast = fast.next;
    slow = slow.next;
}
slow.next = slow.next.next;  // ✂️ remove node
return dummy.next;

🔀 Merge Two Sorted Lists

// ── Merge Two Sorted Lists ───────────────────────────────────────
ListNode dummy = new ListNode(0), tail = dummy;
while (p1 != null && p2 != null) {
    if (p1.val <= p2.val) { tail.next = p1; p1 = p1.next; }
    else                   { tail.next = p2; p2 = p2.next; }
    tail = tail.next;
}
tail.next = (p1 != null) ? p1 : p2;  // append remainder
return dummy.next;

🎯 Practice Problems

#19Remove Nth Node From End of ListMedium #21Merge Two Sorted ListsEasy #23Merge K Sorted Lists — min-heap or divide & conquerHard #138Copy List with Random PointerMedium #2Add Two Numbers — dummy head + carryMedium #61Rotate List — find new tail with offset gapMedium