Linked List Cycle II: Find the Cycle Start

Linked List Cycle II is LeetCode 142. If you have already solved Linked List Cycle (problem 141), you know how to detect whether a cycle exists. This problem takes it one step further: find the exact node where the cycle begins.

Detecting a cycle with Floyd's tortoise and hare is the easy part. The hard part is understanding why a simple pointer reset trick pinpoints the cycle start. That "why" involves a short proof that is worth knowing, because interviewers love to ask about it.

The problem

You are given the head of a linked list. If the list contains a cycle, return the node where the cycle begins. If there is no cycle, return null.

In the example above, the cycle starts at node 2. The tail node (-4) points back to it. Your job is to return a reference to node 2, not just confirm that a cycle exists.

The brute force: hash set

The straightforward approach is the same as for cycle detection. Walk through the list, store every node in a set. The first node you visit twice is the cycle start.

def detectCycle(head):
    seen = set()
    curr = head
    while curr:
        if curr in seen:
            return curr
        seen.add(curr)
        curr = curr.next
    return None

This works and is easy to write. But it uses O(n) space. The interviewer will ask: "Can you do it in O(1) space?" That is where Floyd's algorithm phase two comes in.

Floyd's algorithm: two phases

The O(1) space solution has two phases:

Phase 1: Detect the cycle. Use the standard fast-slow pointer technique. Slow moves 1 step, fast moves 2 steps. If they meet, a cycle exists. If fast reaches null, there is no cycle.

Phase 2: Find the cycle start. Once slow and fast have met somewhere inside the cycle, reset one pointer to the head. Now move both pointers one step at a time. The node where they meet again is the cycle start.

That second phase is the entire trick. It feels like magic the first time you see it. Let's walk through it visually, then prove why it works.

Visual walkthrough

We will use the list 3 -> 2 -> 0 -> -4 -> (back to 2). The cycle starts at node 2 (index 1).

Phase 1 took 3 steps to find the meeting point at node -4. Phase 2 took just 1 step: ptr1 moved from head to node 2, and ptr2 moved from -4 through the cycle back to node 2. They collided at the cycle start.

Why phase 2 works: the math

This is the part that separates people who memorize the solution from people who actually understand it. Let's define some variables:

• F = number of nodes from head to the cycle start (the "tail" length)
• C = the length of the cycle
• a = the distance from the cycle start to the meeting point (measured forward inside the cycle)

When slow and fast meet, slow has traveled F + a steps. Fast has traveled 2(F + a) steps (it moves at double speed). Fast has also completed some number of full laps around the cycle. The difference in distance is a multiple of C:

2(F + a) - (F + a) = kC      for some integer k >= 1
F + a = kC

So F + a is an exact multiple of the cycle length. Rearrange:

F = kC - a

Now here is the key insight. If you start a pointer at the head and another pointer at the meeting point, and move both one step at a time:

• The pointer at the head needs F steps to reach the cycle start.
• The pointer at the meeting point is a steps past the cycle start. After F more steps, it will have traveled a + F = a + kC - a = kC steps from the cycle start. That is exactly k full laps around the cycle. So it lands right back at the cycle start.

Both pointers arrive at the cycle start after exactly F steps. They meet there.

The solution

def detectCycle(head):
    slow = head
    fast = head

    # Phase 1: detect the cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        # fast reached the end, no cycle
        return None

    # Phase 2: find the cycle start
    ptr1 = head
    ptr2 = slow  # the meeting point
    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

Let's break it down:

1. Phase 1 is identical to the basic cycle detection. Two pointers, different speeds. If they meet, break out of the loop. If fast hits null, return None.
2. Phase 2 resets one pointer (ptr1) to head. The other (ptr2) stays at the meeting point. Both now move one step at a time.
3. When ptr1 == ptr2, they are at the cycle start. Return either one.

Complexity analysis

Time: O(n). Phase 1 takes at most O(n) steps for the pointers to meet (same reasoning as basic cycle detection). Phase 2 takes at most F steps, where F is the distance from head to the cycle start. F is at most n. Total: O(n).

Space: O(1). Three pointer variables. No hash set, no extra data structure.

Edge cases

• No cycle. Fast reaches null. Return None.
• Cycle starts at head. F = 0. After phase 1, the reset pointer is already at the cycle start. Phase 2 returns immediately.
• Single node pointing to itself. After one step in phase 1, slow and fast are both at head. Phase 2: ptr1 = head, ptr2 = head. They match immediately. Return head.
• Very long tail (large F, small C). No problem. Phase 2 just takes more steps, but it always converges.

The Building Blocks

This problem is built from one core building block:

Fast-slow pointer (Floyd's cycle detection + cycle start). Phase 1 is the standard cycle detection you already know. Phase 2 is the extension: reset one pointer to head, move both at speed 1, and they meet at the cycle start. The math behind it (F = kC - a) is the proof that makes the whole thing work.

This same two-phase approach shows up in related problems:

• Find the Duplicate Number (LeetCode 287) models an array as an implicit linked list where nums[i] is the "next pointer." The duplicate creates a cycle, and phase 2 of Floyd's algorithm finds it. It is literally this exact problem in disguise.
• Happy Number (LeetCode 202) can use Floyd's to detect if the digit-sum sequence cycles. Once you detect the cycle, you know the number is not happy.
• Linked List Cycle (LeetCode 141) is phase 1 only. If you already know that problem, you are halfway to solving this one.

Why you will forget this (and what to do about it)

The phase 2 reset trick is the piece that slips away. You remember that Floyd's algorithm exists, you remember the fast-slow pointers, but when it comes time to write phase 2 you stall. "Wait, which pointer do I reset? Do both move at speed 1 now? Where do they meet?"

The math proof (F = kC - a) is worth drilling separately. Once that formula is second nature, the code writes itself. You know to reset one pointer to head, keep the other at the meeting point, and advance both by 1 until they collide. No guesswork.

Related posts

• Linked List Cycle - Phase 1 of Floyd's algorithm: detecting whether a cycle exists
• Reverse Linked List - Another fundamental linked list technique that tests pointer manipulation