linked list cycle

Write a function that detects a cycle in a linked-list, and returns the node where the cycle starts.

Solution

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 fast and slow pointers.

The fast and 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

$$time = O(n)$$ $$space = O(1)$$