Linked List Cycle II
Floyd's tortoise & hare — once they meet, restart one pointer from head; both step at speed 1 and converge at the cycle entry.
3 min read
linked-list two-pointers cycle-detection
Problem#
Return the node where the cycle begins in a linked list, or null if none.
Examples#
[3,2,0,-4]with cycle to index 1 → node with value2.[1,2]with cycle to index 0 → node with value1;[1]no cycle →null.
Constraints#
0 <= nodes <= 10^4.
Approach#
Floyd’s algorithm. Phase 1: slow steps 1, fast steps 2; they meet inside the cycle iff one exists. Phase 2: reset slow to head; both step 1 at a time; they meet at the cycle entry.
Solution#
struct ListNode { int val; ListNode* next; };
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 is fast: p = head while p is not 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#
Algebraically: if the head-to-cycle-start distance is a and the meeting point is b steps into the cycle, then 2 (a + b) = a + b + k * C for some integer k, so a = k * C - b. Walking a steps from head and a steps from the meeting point converges at the cycle entry.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#