Problem Description

You are given the head of a linked list and need to find where a cycle begins in the list. If there is no cycle in the linked list, return null.

A cycle exists in a linked list when a node can be reached again by continuously following the next pointers. The problem internally uses pos to indicate the index of the node that the tail's next pointer connects to (0-indexed), where pos = -1 means there is no cycle. Note that pos is not provided as a parameter to your function.

The task is to identify and return the exact node where the cycle starts. You must not modify the linked list structure while solving this problem.

For example, if you have a linked list like 3 -> 2 -> 0 -> -4 where the last node points back to the node with value 2, then the cycle begins at the node with value 2, and you should return a reference to that node.

The solution uses Floyd's Cycle Detection Algorithm (also known as the "tortoise and hare" algorithm) with two phases:

1. Cycle Detection Phase: Use two pointers - a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If a cycle exists, these pointers will eventually meet at some node within the cycle.

2. Cycle Start Detection Phase: Once a cycle is detected, reset one pointer to the head of the list while keeping the other at the meeting point. Move both pointers one step at a time. The node where they meet again is the start of the cycle.

The mathematical proof behind this works because if the distance from head to cycle start is x, the distance from cycle start to where pointers first meet is y, and the remaining distance in the cycle is z, then the relationship x = (k-1) × (y+z) + z holds true (where k is the number of complete cycles the fast pointer traveled). This means moving x steps from both the head and the meeting point will converge at the cycle's starting node.

Intuition

The key insight comes from thinking about what happens when two runners move through a circular track at different speeds. If one runner moves twice as fast as the other, they will eventually meet again somewhere on the track - this forms the basis of cycle detection.

When we have a linked list with a cycle, we can imagine it as a path that leads to a circular loop. Using two pointers moving at different speeds (slow moves 1 step, fast moves 2 steps), if there's a cycle, the fast pointer will eventually "lap" the slow pointer and they'll meet. If there's no cycle, the fast pointer will simply reach the end of the list.

But finding that a cycle exists isn't enough - we need to find where it starts. This is where the mathematical relationship becomes clever. When the pointers meet inside the cycle, they've traveled different distances. The slow pointer traveled distance x + y (where x is the distance to the cycle start, and y is some distance into the cycle). The fast pointer traveled 2(x + y) because it moves twice as fast.

Since the fast pointer is also somewhere in the cycle when they meet, we can express its distance as x + y + k(y + z), where k is the number of complete loops it made, and y + z is the cycle length.

Setting these equal: 2(x + y) = x + y + k(y + z)

Simplifying: x + y = k(y + z)

Therefore: x = k(y + z) - y = (k-1)(y + z) + z

This reveals something remarkable: the distance from the head to the cycle start (x) equals the distance from the meeting point to the cycle start (z) plus some number of complete loops. This means if we place one pointer at the head and keep another at the meeting point, then move both one step at a time, they will meet exactly at the cycle's starting node - because they'll both travel the same distance x to get there.

Solution Approach

The implementation uses Floyd's Cycle Detection Algorithm with two distinct phases:

Phase 1: Detect if a cycle exists

We initialize two pointers, fast and slow, both starting at the head of the linked list. The algorithm moves these pointers through the list:

• slow pointer moves one step at a time: slow = slow.next
• fast pointer moves two steps at a time: fast = fast.next.next

We continue this movement while fast and fast.next are not null (ensuring we don't get null pointer errors). If the pointers meet (slow == fast), we've confirmed a cycle exists. If fast reaches the end of the list, there's no cycle and we return null.

Phase 2: Find the cycle's starting node

Once we've confirmed a cycle exists and have the meeting point, we create a new pointer ans starting at the head of the linked list. We then move both ans and slow pointers one step at a time:

• ans = ans.next
• slow = slow.next

These pointers will meet at the cycle's entrance node. This works because of the mathematical relationship we established: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (plus potentially some complete loops of the cycle).

Why the algorithm works:

Let's trace through the distances:

• Distance from head to cycle entrance: x
• Distance from cycle entrance to meeting point: y
• Distance from meeting point back to cycle entrance: z
• Cycle length: y + z

When the pointers meet:

• Slow pointer traveled: x + y
• Fast pointer traveled: x + y + k(y + z) where k is the number of complete cycles

Since fast moves twice as fast: 2(x + y) = x + y + k(y + z)

Simplifying: x = (k - 1)(y + z) + z

This equation tells us that moving x steps from both the head and the meeting point will converge at the cycle start. The pointer from the meeting point will travel z steps plus potentially (k-1) complete loops before meeting the pointer from the head.

The algorithm has O(n) time complexity where n is the number of nodes, and O(1) space complexity since we only use a constant number of pointers.

Example Walkthrough

Let's walk through a concrete example with the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (the last node points back to node 3, creating a cycle).

Initial structure:
1 -> 2 -> 3 -> 4 -> 5
          ^         |
          |_________|

Phase 1: Cycle Detection

We start with both slow and fast pointers at node 1 (head).

Step 1:

• slow moves to node 2
• fast moves to node 3

Step 2:

• slow moves to node 3
• fast moves from node 3 -> 4 -> 5

Step 3:

• slow moves to node 4
• fast moves from node 5 -> 3 -> 4

Step 4:

• slow moves to node 5
• fast moves from node 4 -> 5 -> 3

Step 5:

• slow moves to node 3
• fast moves from node 3 -> 4 -> 5

Step 6:

• slow moves to node 4
• fast moves from node 5 -> 3 -> 4

The pointers meet at node 4! This confirms a cycle exists.

Phase 2: Finding Cycle Start

Now we place ans pointer at head (node 1) and keep slow at the meeting point (node 4).

Move both pointers one step at a time:

Step 1:

• ans moves from node 1 to node 2
• slow moves from node 4 to node 5

Step 2:

• ans moves from node 2 to node 3
• slow moves from node 5 to node 3

Both pointers meet at node 3 - this is where the cycle begins!

Verification of the math:

• Distance from head to cycle start (x) = 2 steps (1 -> 2 -> 3)
• Distance from cycle start to meeting point (y) = 2 steps (3 -> 4)
• Distance from meeting point back to cycle start (z) = 2 steps (4 -> 5 -> 3)
• Cycle length = 3 nodes (3 -> 4 -> 5 -> 3)

When they first met:

• Slow traveled: x + y = 2 + 2 = 4 steps
• Fast traveled: 2(x + y) = 8 steps = x + y + k(y + z) = 2 + 2 + 1×3 + 1 (one complete cycle plus one extra step)

The equation x = z holds true here (both equal 2), so moving 2 steps from both the head and meeting point converges at node 3, the cycle's start.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list.

The algorithm uses Floyd's Cycle Detection (Tortoise and Hare) approach. In the worst case:

• The first while loop runs until the slow and fast pointers meet inside the cycle. The slow pointer travels at most n nodes before meeting the fast pointer.
• The second while loop runs to find the start of the cycle. This loop runs at most n iterations as it traverses from the head to the cycle's starting point.
• Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Three pointer variables: fast, slow, and ans
• No additional data structures are created regardless of the input size
• The space usage remains constant independent of the number of nodes in the linked list.

Common Pitfalls

1. Incorrect Cycle Detection Check

A common mistake is checking if the pointers meet before moving them, which causes the algorithm to miss cycles when the head itself is part of the cycle.

Incorrect Implementation:

while fast_pointer and fast_pointer.next:
    # Wrong: checking before moving
    if slow_pointer == fast_pointer:
        # This will never trigger on first iteration
        break
    slow_pointer = slow_pointer.next
    fast_pointer = fast_pointer.next.next

Solution: Always move the pointers first, then check for equality. This ensures that even if both pointers start at the same position (head), they separate and can properly detect the cycle.

2. Not Handling Edge Cases Properly

Failing to check for null values before accessing fast_pointer.next.next can cause runtime errors.

Incorrect Implementation:

# Dangerous: not checking fast_pointer.next
while fast_pointer:
    slow_pointer = slow_pointer.next
    fast_pointer = fast_pointer.next.next  # Can throw error if fast_pointer.next is None

Solution: Always check both fast_pointer and fast_pointer.next before advancing the fast pointer two steps.

3. Confusing the Meeting Point with Cycle Start

A critical misunderstanding is thinking that where the pointers first meet is the cycle's starting point. The meeting point is typically somewhere within the cycle, not at its entrance.

Incorrect Implementation:

while fast_pointer and fast_pointer.next:
    slow_pointer = slow_pointer.next
    fast_pointer = fast_pointer.next.next
    if slow_pointer == fast_pointer:
        return slow_pointer  # Wrong: this is the meeting point, not cycle start

Solution: After detecting a cycle, implement Phase 2 where you reset one pointer to head and move both pointers one step at a time until they meet at the cycle's entrance.

4. Moving Pointers at Wrong Speed in Phase 2

In the second phase, both pointers must move at the same speed (one step at a time). Moving them at different speeds will not find the cycle start.

Incorrect Implementation:

# After detecting cycle
start_pointer = head
while start_pointer != slow_pointer:
    start_pointer = start_pointer.next
    slow_pointer = slow_pointer.next.next  # Wrong: should move one step only

Solution: In Phase 2, both pointers must advance exactly one step per iteration to ensure they meet at the cycle's starting node.

5. Single Node Self-Loop Edge Case

When a single node points to itself, both pointers might not separate properly if the initial check is done incorrectly.

Robust Implementation:

def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return None
      
    fast_pointer = slow_pointer = head
  
    # Phase 1: Detect cycle
    while fast_pointer and fast_pointer.next:
        slow_pointer = slow_pointer.next
        fast_pointer = fast_pointer.next.next
      
        if slow_pointer == fast_pointer:
            # Phase 2: Find cycle start
            start_pointer = head
            while start_pointer != slow_pointer:
                start_pointer = start_pointer.next
                slow_pointer = slow_pointer.next
            return start_pointer
  
    return None

This implementation correctly handles all edge cases including empty lists, single nodes, and self-loops.