DSA sheet · Linked List · Fast & slow pointer pattern

Linked List Cycle II

The previous problem only asked whether there is a cycle. This one asks where it starts. The teacher reuses the same two runners to find a meeting point, and then adds one surprising trick: put one pointer back at the head, move both one step at a time, and they meet exactly at the start of the cycle. The code is tiny. The real lesson is the proof of why the trick works, because, as she says, writing this code in an interview without being able to explain it doesn't make sense. So the proof gets the most space on this page.

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

• Part 0 · What you must know before starting
• Part A · Find the cycle start with fast and slow pointers
• · inside Part A, step 4: the distance proof (with picture)
• Part B · Revision page

Part 0 · Before starting

Linked list basics

A linked list is a chain of nodes. Each node has a val (the number) and a next (the node after it). The last node's next is None. We are given only the first node, called head.

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

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

• Walking: curr = head, then curr = curr.next repeatedly until curr is None.
• No index access: there is no list[i]. Reaching position i means walking i steps, so it costs O(n).
• Keep head safe: move copies (slow, fast, …), never head itself.
• Save next before changing a pointer: if you overwrite node.next without saving the old value, the rest of the list is lost. (Here we never change any pointer; we only walk.)

Cycle words used on this page

• Cycle: some node's next points back to an earlier node, so the walk never reaches None.
• Tail part: the nodes before the loop (from head up to, but not including, the first loop node).
• Cycle start: the first node of the loop, the one that two different nodes point to (one from the tail part, one from the end of the loop). This is the answer.
• Cycle length K: how many nodes are in the loop (= how many steps it takes to go round once).

[1] → [2] → [3] → [4] → [5] → [6]
             ↑                   │
             └───────────────────┘
tail part: 1, 2     cycle start: 3     loop: 3 4 5 6  (K = 4)

Fast and slow pointers (recap from Cycle I and Middle of List)

• slow moves 1 node per step, fast moves 2. Both start at head. So fast always has gone exactly twice as far as slow.
• Loop condition while fast and fast.next: even length → fast becomes None; odd length → fast.next becomes None. Both mean "the list ends", so no cycle.
• If there is a cycle, fast laps round and catches slow: they land on the same node. In Cycle I we just returned True there. Now we need more.

Part A · Find the cycle start with fast and slow pointers

LeetCode 142

1The question in simple words

You get the head of a linked list. If it has a cycle, return the node where the cycle starts. If it has no cycle, return None (null). Don't change the list.

The teacher goes through LeetCode's three examples:

[3] → [2] → [0] → [-4]
       ↑            │
       └────────────┘

[1] → [2]
 ↑     │
 └─────┘

[1] → None

• Example 1: the last node (−4) points back to the node with 2, so the loop starts there.
• Example 2: the loop starts at the very first node (index 0), so the answer is head itself.
• Example 3: no loop, so there is no start → None.

LeetCode shows a number pos (the index the last node links back to). The teacher points out it is not passed to your function. It only helps you read the example.

2What the constraints tell us

• Number of nodes: 0 to 10⁴ → the list can be empty, and then we must return None without crashing.
• Time limit: very roughly, about 10⁸ simple operations per second is the ceiling before TLE (Time Limit Exceeded). With n = 10⁴, even n² = 10⁸ is on the edge. But the teacher's point is that in linked lists we almost always write linear code, brute force or optimal, so TLE isn't the worry here.
• The follow-up on LeetCode asks for O(1) extra memory. That rules out the hash set idea (see Doubt 1) and pushes us to pointers.

3Intuition: why this pattern, and the two-phase idea

The teacher first picks the pattern by elimination. The linked list patterns are: basic operations, fast and slow pointers, reversal, and merge/sort.

• Reversal? No. Nothing here needs reversing.
• Merge / sort? No. There's nothing to merge or sort.
• Fast and slow? Yes. We just used it to detect a cycle (runners at speeds 1 and 2 must meet on a loop), and this question is about the same cycle. It's also about a "meeting point", which is the classic sign for this pattern.

The plan has two phases:

1. Phase 1, detect: run slow (1 step) and fast (2 steps) until they meet. The meeting node proves there is a cycle, but it is usually not the start.
2. Phase 2, locate: leave slow at the meeting node. Put a second pointer at head. Move both at the same speed, 1 step each. The node where they meet is the cycle start.

4Building the logic, and the proof

Phase 1 gives a meeting point, not the start

Take this list (the cycle starts at node 3):

[1] → [2] → [3] → [4] → [5] → [6]
             ↑                   │
             └───────────────────┘

slow/fast go: (1,1) → (2,3) → (3,5) → (4,3) → (5,5). They meet at 5. But the loop starts at 3. So returning the meeting node would be wrong. The meeting node only tells us "a cycle exists".

Phase 2: reset one pointer to head, same speed

Keep slow on 5. Start a new pointer at head (the teacher reuses fast for this, or calls it a "new node" pointer). Now both move 1 step:

• new = 1, slow = 5 → different → new = 2, slow = 6
• new = 2, slow = 6 → different → new = 3, slow = 3
• new = 3, slow = 3 → same → node 3 is the start ✓

Why should that work? It looks like magic. Here is the proof, the way the teacher builds it.

The distance proof

Give names to three distances (all measured in "steps", i.e. number of next links followed):

         a = 2 steps                 b = 2 steps
   [1] ─────→ [2] ─────→ [3] ─────→ [4] ─────→ [5]
   head                   S ↑                    │ M
                            │                    │
                            └───── [6] ←─────────┘
                                 c = 2 steps

   a = head → S   (length of the tail part)
   b = S → M      (from the cycle start to the meeting point, going forward)
   c = M → S      (the rest of the loop, from the meeting point back to the start)
   K = b + c      (cycle length; here K = 4)

S = cycle start, M = meeting point of phase 1.

1. How far did slow walk until the meeting? From head to S (a), then from S to M (b). So slow = a + b.
2. How far did fast walk? The same a and b, plus some whole trips round the loop, because it went round and came up behind slow. One trip is K steps. It might have gone round once, twice, or more, so say n full trips: fast = a + b + n·K (n ≥ 1).
3. Fast always walks twice as far as slow (that's what speed 2 vs 1 means, the same fact that puts slow at the middle in the middle-of-list problem): fast = 2 · slow.
4. Put the two together: 2(a + b) = a + b + n·K.
5. Take away a + b from both sides: a + b = n·K.
6. Move b across: a = n·K − b.

What does n·K − b mean on the picture? Take the teacher's case n = 1: a = K − b. The whole loop is K. Remove the part b (S → M). What's left is exactly c, the walk from M forward back to S. So:

Check it on the picture: a = 2 (1 → 2 → 3) and c = 2 (5 → 6 → 3). Equal ✓. And slow walked a + b = 4, fast walked 8 = 4 + 1·4, so n = 1 ✓.

The special case: cycle at the head (Example 2)

Here a = 0. Phase 1 meets somewhere in the loop; with a = 0 the proof says b = n·K, which means M is a whole number of laps away from S, i.e. M is S itself (the head). In practice both runners start on head and meet again on head after slow's first lap (Doubt 2). In phase 2 the new pointer starts at head and slow is already on head, so they are equal before any move. That's why phase 2 must check while slow is not ptr before moving: we return head straight away ✓.

5Approach steps

1. slow = fast = head.
2. While fast and fast.next exist: slow moves 1, fast moves 2.
3. If slow is fast (they met): set ptr = head. While ptr is not slow, move both one step. Return ptr (the cycle start).
4. If the first loop ends without meeting → no cycle → return None.

6Code (Python)

class Solution:
    def detectCycle(self, head):
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next              # phase 1: speed 1
            fast = fast.next.next         #          speed 2
            if slow is fast:              # met inside the loop
                ptr = head                # phase 2: new pointer at head
                while ptr is not slow:    # same speed until they meet
                    ptr = ptr.next
                    slow = slow.next
                return ptr                # this is the cycle start
        return None                       # fast fell off: no cycle

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5 → 6 → back to 3 (a = 2, K = 4).

end of phase 1 (step 4):
[1] → [2] → [3] → [4] → [5] → [6]
             ↑             ↑     │
             │       slow, fast  │
             └───────────────────┘

start of phase 2 (step 5):
[1] → [2] → [3] → [4] → [5] → [6]
 ↑           ↑             ↑     │
ptr          │           slow    │
             └───────────────────┘

end of phase 2 (step 7):
[1] → [2] → [3] → [4] → [5] → [6]
             ↑                   │
         ptr, slow               │
             └───────────────────┘   → answer: node 3

The other examples

• Example 1 [3, 2, 0, −4], back to index 1: phase 1 → (2,0), (0,2), (−4,−4): meet at −4. Phase 2: ptr = 3, slow = −4 → step → ptr = 2, slow = 2 → return the node with 2 ✓ (a = 1, c = 1).
• Example 2 [1, 2], back to index 0: phase 1 → (2,1), (1,1): meet at 1 = head. Phase 2: ptr = head is already slow → return head ✓.
• Example 3 [1]: fast.next is None → loop never runs → None ✓.
• Empty list: fast is None → None ✓.

9Complexity & remember

• Time O(n). The teacher notes it isn't exactly n: fast may go round the loop several times before meeting, so the work is like 2n or 3n, some constant × n. Phase 2 adds a ≤ n more steps. A constant times n is still linear, so O(n).
• Space O(1): only a few pointer variables.

The teacher's interview tip: remember the proof, not just the code. If you write "reset to head and move both" without explaining a + b = nK, it looks memorised.

Part B · Revision page

class Solution:
    def detectCycle(self, head):
        seen = set()
        curr = head
        while curr is not None:
            if curr in seen:        # first node met twice = cycle start
                return curr
            seen.add(curr)
            curr = curr.next
        return None

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

def build(values, pos=-1):
    """Build a list; if pos >= 0, the last node links back to the node at index pos."""
    nodes = [ListNode(v) for v in values]
    for x, y in zip(nodes, nodes[1:]):
        x.next = y
    if pos >= 0 and nodes:
        nodes[-1].next = nodes[pos]
    return nodes[0] if nodes else None

s = Solution()
print(s.detectCycle(build([1, 2, 3, 4, 5, 6], 2)).val)   # 3
print(s.detectCycle(build([3, 2, 0, -4], 1)).val)        # 2
print(s.detectCycle(build([1, 2], 0)).val)               # 1
print(s.detectCycle(build([1])))                         # None
print(s.detectCycle(None))                               # None

Based on this video: Linked List Cycle II | Fast and Slow Pointer with proof