linked list cycle
Write a function that detects a cycle in a linked-list, and returns the node where the cycle starts.
Detecting the cycle
Detecting whether a linked-list has a cycle in it, in O(1) space has an interesting solution: one can simply iterate over it with
slow pointers can meet anywhere within the cycle. They do not have to necessarily meet on node
4. Finding the starting node of the cycle involves an extra step.
Finding the start of the cycle
Finding the start of the cycle simply requires simultaneously stepping from the intersection node (
4) and the
head of the list.
1def detectCycle(head): 2 slow = fast = head 3 while fast and fast.next: 4 fast, slow = fast.next.next, slow.next 5 if slow == fast: 6 break 7 8 if fast and fast.next: 9 slow = head 10 while slow != fast: 11 slow, fast = slow.next, fast.next 12 return slow
Time and Space Complexity