2. How do I find the middle without knowing the length?

Move `fast` twice as fast as `slow`. When `fast` has covered the whole list, `slow` has covered half of it. Loop while `fast && fast->next`; on an even length this stops `slow` on the **second** middle.

3. Why does fast always catch slow in a loop?

Once both are inside the loop, each move puts `fast` **one node closer** to `slow` (it moves 2, slow moves 1). The gap shrinks by exactly 1 each time, so it hits 0 — `fast` can't jump over `slow`. If there's no loop, `fast` reaches `null` first.

4. Where does the cycle start?

Not at the meeting node. Let `a` = steps from the head to the entry, and `b` = steps from the entry to the meeting node. `fast` walked twice as far as `slow`, which works out to `a = (some whole number of loops) − b`. So a pointer from the **head** and one from the **meeting node**, both moving 1 step, arrive at the entry together.

5. How do I reach the n-th node from the end in one pass?

Give `fast` a head start of `n` nodes, then move both 1 step until `fast` falls off the end. The gap never changes, so `slow` ends `n` nodes from the end. To **delete** that node you need the one before it: use a gap of `n + 1` and start both on a **dummy** node.

O(N) time — each pointer walks the list at most a few times — and O(1) extra space, because you only keep two pointers. That O(1) space is the whole point; the brute forces are usually O(N) time too, but with O(N) space.

Linked List — Fast & Slow Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Q: 1. What would brute force do?

Copy the nodes into a `vector` so you can index them (`v[n/2]`, `v[n-k]`), or keep a `set` of visited nodes to spot a loop. That's O(N) extra space. Or count the length in one pass and walk again in a second pass.

Q: What is the difference between Where slow and fast meet and Where the cycle starts?

They meet **somewhere inside** the loop. The entry is found in phase 2: one pointer from the head, one from the meeting node, both 1 step at a time.

Q: What is the difference between First middle and Second middle?

`while (fast && fast->next)` with both at `head` stops on the **second** middle of an even list. `while (fast->next && fast->next->next)` stops on the **first**. Pick the one the problem (or the split) needs.

Q: What is the difference between Gap of n and Gap of n + 1?

Gap `n`: `slow` lands **on** the n-th node from the end — fine for reading or swapping it. Gap `n + 1` (starting from a dummy): `slow` lands **before** it — needed to delete it.

Q: What is the difference between Comparing nodes and Comparing values?

Cycles and intersections are about the **same node object** (`a == b`), not equal values. Two different nodes can both hold `1`. Palindrome and twin sum are the opposite: they compare `val`.

Move two pointers at different speeds (or with a fixed gap) to find cycles, middles, and the k-th node from the end in one pass.

3 sub-patterns · 13 questions

Remember this · Linked List — Fast & Slow

Trigger

Cycle detection, middle of list, "n-th from end", two lists meeting, repeating sequences.

Think

If one pointer moves faster or starts earlier, where will they meet?

Key question

What speed or gap makes the meeting point tell me the answer?

What is this pattern?

A linked list can only be walked forward, one node at a time. You can't jump to index n/2, you can't read it backwards, and you don't know its length until you reach the end. Fast & Slow gets around this with two pointers that move differently, so that where one of them stops tells you something about the other.

There are two ways to make them differ:

Different speeds. slow moves 1 node, fast moves 2. When fast reaches the end, slow is in the middle. If the list has a loop, fast never reaches the end — it goes round and catches up with slow from behind.
Same speed, a head start (gap). fast goes n steps first, then both move 1 at a time. When fast reaches the end, slow is n nodes from the end.

The brute force usually stores nodes in a vector or a set (O(N) extra space) or walks the list twice. The pattern does it in one pass with O(1) extra space.

Two runners on a track. If the track is a straight road, the fast runner reaches the finish line while the slow one is exactly halfway. If the track is a loop, the fast runner keeps going round and eventually laps the slow one — so the two meeting proves the track is a loop.

See it move

Cells are the nodes in `next` order. The last cell `↩ 2` (orange) means the tail's `next` points back to node 2. Blue = where slow and fast met; purple = the cycle entry.

Floyd's cycle detection: meet, then find the entrylist = [3,1,4,1,5,9,2], tail → node 2step 1/9

list

↩ 2

▲slow fast

idx

State

slow: node 0
fast: node 0
moves: 0

phase 1: meet

The list is 3 → 1 → 4 → 1 → 5 → 9 → 2, and the tail's next goes back to node 2 (the ↩ 2 cell). Both pointers start at the head.

`D` is a dummy node before the head and `null` is the end of the list. The blue band is the gap between slow and fast. Red = the removed node; blue = the node whose `next` changes.

Fixed gap: remove the n-th node from the endlist = [10,20,30,40,50], n = 2step 1/8

list

null

▲slow fast

State

n: 2
gap: 0

remove the 2nd node from the end

Add a dummy node D before the head, so removing the real head needs no special case. Both pointers start on D.

How do I recognise it?

The input is a linked list and the question asks for the middle, the n-th node from the end, or whether there's a cycle and where it starts.
The follow-up says "O(1) extra memory" or "in one pass" — that rules out copying into a vector or a hash set.
Two lists that may join: find where they meet (they share a tail).
A sequence that keeps applying the same rule (n → sum of squared digits, i → nums[i], i → i + nums[i]): it's an invisible linked list that must either end or loop.
You need to split a list in half, or compare the first half with the second half (palindrome, twin sums).
The brute force stores every visited node in a set, or counts the length first and then walks again.

Looks like Linked List — Fast & Slow, but isn't

Reverse a list, or reverse it in groups of k

→ Linked List — In-place Reversal

Reversal rewires next pointers with prev / curr / next. Fast & Slow only finds positions. Palindrome and twin sum use both: fast & slow to find the middle, then reversal for the second half.

Two pointers moving toward each other on a sorted array

→ Two Pointers (opposite ends)

An array has a back, so one pointer can start at the end. A singly linked list has no way to walk backwards, which is why we use speed or a gap instead.

Find the duplicate in an array of 1..n

→ Cyclic Sort (if you may change the array)

Placing each value at its home index is simpler when writes are allowed. Only when the array is read-only and you need O(1) space do you treat i → nums[i] as a list and run Floyd.

Merge two or k sorted lists

→ K-way Merge

Merging compares the heads of several lists and always takes the smallest. Nothing moves at a different speed and there's no cycle or gap.

How would I discover it from scratch?

Don't memorise “use linked list — fast & slow”. Ask these questions in order — the pattern falls out.

Copy the nodes into a vector so you can index them (v[n/2], v[n-k]), or keep a set of visited nodes to spot a loop. That's O(N) extra space. Or count the length in one pass and walk again in a second pass.

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

Cycle detection

6 questions

Slow moves 1, fast moves 2. If fast reaches null, there's no cycle. If they meet, there is one. To find where it starts, reset one pointer to the head and move both 1 step until they meet again.

Middle / split

4 questions

Slow moves 1, fast moves 2; when fast reaches the end, slow is in the middle. Use the middle to split the list, then often reverse the second half to compare it with the first.

Gap / alignment

3 questions

Both pointers move at the same speed, but one starts ahead (by n nodes, or by the difference in the lists' lengths), so they reach the target at the same moment.

Don't mix these up

Where slow and fast meet vs Where the cycle starts

They meet somewhere inside the loop. The entry is found in phase 2: one pointer from the head, one from the meeting node, both 1 step at a time.

First middle vs Second middle

while (fast && fast->next) with both at head stops on the second middle of an even list. while (fast->next && fast->next->next) stops on the first. Pick the one the problem (or the split) needs.

Gap of n vs Gap of n + 1

Gap n: slow lands on the n-th node from the end — fine for reading or swapping it. Gap n + 1 (starting from a dummy): slow lands before it — needed to delete it.

Comparing nodes vs Comparing values

Cycles and intersections are about the same node object (a == b), not equal values. Two different nodes can both hold 1. Palindrome and twin sum are the opposite: they compare val.

Code templates (C++)

Floyd: detect a cycle and find its start

Loop on fast && fast->next (check fast first, or you crash on null). Compare nodes, not values. For "is there a cycle?" return true at the meeting; for the start, run phase 2.

floyd-template.cpp

// Floyd's cycle detection: slow moves 1, fast moves 2.
// Returns the node where the cycle starts, or nullptr if there is no cycle.
ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {               // check fast BEFORE fast->next
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                    // phase 1: they met inside the loop
            ListNode* p = head;                // phase 2: one from head, one from the meeting node
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;                          // both 1 step at a time → they meet at the entry
        }
    }
    return nullptr;                            // fast fell off the end → no cycle
}

Middle of the list

slow = fast = head gives the second middle on even length. To delete the middle or cut the list, you need the node before it: start fast two nodes ahead.

middle-template.cpp

// Middle of a list: when fast reaches the end, slow is halfway.
// Even length → returns the SECOND middle (1→2→3→4 gives 3).
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Node just BEFORE the middle (to delete it or cut the list in two).
// Needs at least 2 nodes. Fast starts 2 ahead, so slow stops one node earlier.
ListNode* beforeMiddle(ListNode* head) {
    ListNode *slow = head, *fast = head->next->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Middle + reverse the second half

Find the middle, reverse from there, then walk the first half and the reversed second half together. Reverse it back before returning if the caller still uses the list.

half-reverse-template.cpp

// Compare the first half with the second half read backwards
// (palindrome, twin sums) in O(1) extra space.
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* second = reverseList(slow);       // odd length: middle ends up in the second half, harmless
    bool ok = true;
    for (ListNode *a = head, *b = second; b; a = a->next, b = b->next)
        if (a->val != b->val) { ok = false; break; }
    reverseList(second);                        // put the list back the way you found it
    return ok;
}

Fixed gap: n-th from the end

Use a dummy node so removing the head is not a special case. A gap of n + 1 leaves slow just before the target; a gap of n leaves it on the target (enough when you only read it).

gap-template.cpp

// Remove the n-th node from the end in one pass.
// fast goes n + 1 steps ahead of slow; when fast hits null, slow is just BEFORE the target.
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);                   // dummy: removing the head is not a special case
    ListNode *slow = &dummy, *fast = &dummy;
    for (int i = 0; i <= n; i++) fast = fast->next;   // gap of n + 1
    while (fast) { slow = slow->next; fast = fast->next; }
    ListNode* target = slow->next;
    slow->next = target->next;                 // unlink it
    delete target;
    return dummy.next;
}

Start with Cycle detection