Linked List Cycle II — Floyd's Cycle Start Detection

Problem 228 · Linked List Cycle II

Difficulty: Medium · Pattern: Floyd's Cycle Detection (find entry)

Return the node where the cycle begins.

Intuition

After slow and fast meet:

Reset one pointer to head
Move both one step at a time
They meet at cycle entry

Math: When they first meet, slow has traveled d + m steps, fast d + m + k·c steps. Since fast = 2×slow: d = k·c - m, so from head and from meeting point, both reach entry in same steps.

Solutions

# Python
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next; slow = slow.next
            return ptr
    return None

// Java
public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {
            ListNode ptr = head;
            while (ptr != slow) { ptr = ptr.next; slow = slow.next; }
            return ptr;
        }
    }
    return null;
}

// C++
ListNode *detectCycle(ListNode *head) {
    ListNode *slow=head, *fast=head;
    while (fast && fast->next) {
        slow=slow->next; fast=fast->next->next;
        if (slow==fast) {
            ListNode *ptr=head;
            while (ptr!=slow) { ptr=ptr->next; slow=slow->next; }
            return ptr;
        }
    }
    return nullptr;
}

Complexity

Time: O(n)
Space: O(1)