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 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
 4     fast, slow =,
 5     if slow == fast:
 6         break
 8 if fast and
 9     slow = head
10     while slow != fast:
11         slow, fast =,
12     return slow

Time and Space Complexity