Linked List Cycle II

How it works

Floyd's cycle detection uses two pointers moving at different speeds. If there's a cycle, the fast pointer (moving 2 steps) will eventually meet the slow pointer (moving 1 step) inside the cycle. The key insight is mathematical: when they meet, if we reset one pointer to the head and move both at the same speed, they will meet again at the cycle's start. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going around the cycle).

Steps

1. Initialize both slow and fast pointers at the head.
2. Move slow by 1 step and fast by 2 steps until they meet or fast reaches the end.
3. If fast reaches null, return null (no cycle).
4. When they meet inside the cycle, reset slow to the head.
5. Move both pointers one step at a time until they meet again.
6. Return the meeting point, which is the cycle's start.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Returning the Meeting Point Instead of the Cycle Start

When the slow and fast pointers first meet, that meeting point is inside the cycle but is not necessarily the cycle's starting node. You must perform the second phase: reset one pointer to the head and move both pointers one step at a time until they meet again at the actual cycle start.

Forgetting to Handle Lists Without Cycles

If the fast pointer reaches null, the list has no cycle and the function should return null. Skipping this check and proceeding to the second phase causes null pointer exceptions when trying to find a cycle start that does not exist.

Incorrect Pointer Reset in the Second Phase

After detecting the meeting point, one pointer must be reset to the head while the other stays at the meeting point. A common error is resetting both pointers or resetting to the wrong position, which causes the second phase to find an incorrect node or loop indefinitely.

from typing import Optional

# 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]:
        if not head or not head.next:
            return None

        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        if (!head || !head->next) {
            return nullptr;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};