Linked List Cycle II
Find the node where a cycle begins using Floyd's two-phase detection.
3 min read
fast-slow linked-list
Problem#
Return the node where a cycle in the linked list begins, or nullptr if no cycle exists.
Examples#
[3,2,0,-4]with tail → index 1 → node with value2.[1, 2]no cycle →nullptr.
Constraints#
- Length in
[0, 10^4].
Hints#
Hint 1
After tortoise-hare meet inside the cycle, distance from list-head to cycle-start equals distance from meeting-point to cycle-start (mod cycle length).
Approach#
Phase 1: tortoise/hare meet inside the cycle (if any). Phase 2: reset one pointer to head; advance both at speed 1; they meet at the cycle’s entry.
Solution#
class Solution {public: ListNode* detectCycle(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode* p = head; while (p != slow) { p = p->next; slow = slow->next; } return p; } } return nullptr; }};func detectCycle(head *ListNode) *ListNode { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { p := head for p != slow { p = p.Next slow = slow.Next } return p } } return nil}from typing import Optional
class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: p = head while p != slow: p = p.next slow = slow.next return p return Nonefunction detectCycle(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { let p = head; while (p !== slow) { p = p.next; slow = slow.next; } return p; } } return null;}class Solution { 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 p = head; while (p != slow) { p = p.next; slow = slow.next; } return p; } } return null; }}function detectCycle(head: ListNode | null): ListNode | null { let slow = head, fast = head; while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; if (slow === fast) { let p = head; while (p !== slow) { p = p!.next; slow = slow!.next; } return p; } } return null;}Editorial#
Let L = head-to-cycle distance, C = cycle length, D = distance from cycle-entry to meeting point. At meet: slow has walked L + D, fast L + D + kC for some k ≥ 1. From 2(L+D) = L + D + kC we get L = kC - D, i.e., walking L steps from the meeting point lands at the cycle entry. The second loop exploits this exactly.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#