LeetCode 142: Linked List Cycle II

Problem Restatement

We are given the head of a linked list.

If the linked list contains a cycle, return the node where the cycle begins.

If there is no cycle, return None.

LeetCode internally represents the cycle using an index pos, where the tail points back to the node at index pos. This value is not passed into the function. (leetcode.com)

Examples

Example 1:

3 -> 2 -> 0 -> -4
     ^         |
     |_________|

The cycle begins at the node with value 2.

Output:

node with value 2

Example 2:

1 -> 2
^    |
|____|

The cycle begins at the node with value 1.

Example 3:

1 -> None

There is no cycle.

Output:

None

Input and Output

Function shape:

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...

Relation to LeetCode 141

LeetCode 141 only asks:

Does a cycle exist?

LeetCode 142 asks a harder question:

Where does the cycle begin?

We still use Floyd’s tortoise and hare algorithm.

But after detecting the cycle, we perform one more step to locate the entry node.

First Step: Detect Whether a Cycle Exists

Use two pointers:

If no cycle exists:

fast

eventually reaches None.

If a cycle exists:

slow == fast

at some node inside the cycle.

This part is identical to LeetCode 141.

Key Insight

After the two pointers meet:

1. Move one pointer back to the head.
2. Keep the other pointer at the meeting point.
3. Move both pointers one step at a time.
4. The node where they meet again is the cycle entry.

This looks surprising at first.

The reason comes from the distance relationships inside the cycle.

Mathematical Proof

Define:

So the total cycle length is:

b + c

When the pointers meet:

• slow traveled:

a + b

• fast traveled:

2(a + b)

But fast also traveled exactly one extra full cycle more than slow.

So:

2(a + b) = a + b + k(b + c)

for some integer k >= 1.

Simplify:

a + b = k(b + c)

Rearrange:

a = k(b + c) - b

For the first meeting, think of one cycle difference:

a = c

modulo the cycle length.

That means:

• starting from the head and walking a steps reaches the cycle entry
• starting from the meeting point and walking c steps also reaches the cycle entry

So if:

1. one pointer starts at the head
2. one pointer starts at the meeting point
3. both move one step at a time

they meet exactly at the cycle entry.

Example Walkthrough

Consider:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|

The cycle entry is node 3.

Suppose the pointers meet at node 5.

Now:

• move one pointer to the head
• keep one pointer at 5

Move both one step:

Depending on cycle length and meeting location, they eventually synchronize at the cycle entry.

The formal proof guarantees this.

Algorithm

Phase 1:

1. Use slow and fast pointers.
2. Detect whether a cycle exists.

Phase 2:

If a meeting occurs:

1. Set:

ptr1 = head
ptr2 = meeting_node

2. Move both one step at a time.
3. When they meet, return that node.

If no cycle exists, return None.

Correctness

If the linked list has no cycle, the fast pointer eventually reaches None, so the algorithm correctly returns None.

Now suppose the list contains a cycle.

By Floyd’s cycle detection argument, the slow and fast pointers eventually meet inside the cycle.

Let:

At the meeting point, the fast pointer has traveled one whole cycle more than the slow pointer, so:

2(a + b) = a + b + kL

which simplifies to:

a + b = kL

Therefore:

a = kL - b

This means the distance from the meeting point to the cycle entry equals the distance from the head to the cycle entry modulo the cycle length.

So if one pointer starts at the head and another starts at the meeting point, and both move one step at a time, they meet exactly at the cycle entry.

Therefore, the algorithm correctly returns the node where the cycle begins.

Complexity

Let n be the number of nodes.

Implementation

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                ptr1 = head
                ptr2 = slow

                while ptr1 != ptr2:
                    ptr1 = ptr1.next
                    ptr2 = ptr2.next

                return ptr1

        return None

Code Explanation

Initialize two pointers:

slow = head
fast = head

Move them at different speeds:

slow = slow.next
fast = fast.next.next

If they meet:

if slow == fast:

a cycle exists.

Now:

ptr1 = head
ptr2 = slow

One pointer starts from the head.

The other starts from the meeting point.

Move both one step:

while ptr1 != ptr2:
    ptr1 = ptr1.next
    ptr2 = ptr2.next

When they meet again:

return ptr1

that node is the cycle entry.

If no meeting ever occurs:

return None

the list has no cycle.

Why Returning slow Immediately Is Wrong

The first meeting point is not necessarily the cycle entry.

Example:

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|

The cycle entry is 3.

But the first meeting may happen at 4 or 5.

So we need the second phase to locate the true entry node.

Testing

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

def run_tests():
    s = Solution()

    a = ListNode(3)
    b = ListNode(2)
    c = ListNode(0)
    d = ListNode(-4)

    a.next = b
    b.next = c
    c.next = d
    d.next = b

    assert s.detectCycle(a) == b

    a = ListNode(1)
    b = ListNode(2)

    a.next = b
    b.next = a

    assert s.detectCycle(a) == a

    a = ListNode(1)

    assert s.detectCycle(a) is None

    a = ListNode(1)
    b = ListNode(2)
    c = ListNode(3)

    a.next = b
    b.next = c

    assert s.detectCycle(a) is None

    a = ListNode(1)
    a.next = a

    assert s.detectCycle(a) == a

    print("all tests passed")

run_tests()

Test meaning: