Problem
Detect the cycle in a Linked list, return the starting Node of the cycle if any, otherwise return NULL. E.g: return Node 2 in following linked list:
Algorithm
Let fast and slow be 2 pointers, initial point to head of the linked list. The algorithm consists of 2 while loops:
- In the first loop, we move slow 1 step and fast 2 steps in each iterator until either of them reaches the list's tail. If at any point of the loop, slow and fast point to the same node => there is a cycle in the linked list, we break. Otherwise, return NULL as there is no cycle.
ListNode* fast = head;
ListNode* slow = head;
bool hasCycle = false;
while (fast && fast->next && slow) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
hasCycle = true;
break;
}
}
if (!hasCycle) return NULL;
- In the second loop, we reset slow to head, fast stay the same at the meeting node in the first loop. Now we move both one by one step until they meet again. This meeting point is the starting point of the cycle.
slow = head;
while (fast != slow) {
slow = slow->next;
fast = fast->next;
}
return fast;
Proof
- Let L be the length of the cycle (if any).
- First of all, if fast and slow don't meet in the first loop, obviously there is no cycle. Because, if there is a cycle, sooner or later, fast and slow will be in the cycle and they will be there forever. In the cycle, the distance between them will increase by 1 after each iteration. When the distance is divisible by L, they will meet.
- Let X be the starting point of the cycle (green node).
- Let Y be the meeting point in the first loop (red node).
- Let M be the length from head to X , K be the length from X to Y
- We have:
-
in the first loop
- slow moved: M + L * s + K steps (s is an integer)
- fast moved: M + L * f + K steps (f is an integer)
- as fast moves 2 times faster than slow:
M + L * f + K = 2 * (M + L * s + K)
<=> M + L(2s - f) + K = 0
<=> M + K = L(f - 2s)
So M + K is length of the cycle times an integer. So from Y, if we move M more steps, we will arrive X. The problem is that we don't know M.
-
Notice that distance from head to X is also M, so if we move M steps from both head and Y, we will meet at X. That lead to the second loop.
-
Runtime: to go into the cycle, slow needs N-L steps, i.e the first loop cost O(N-L). Once be inside the cycle, slow and fast need < L steps to meet each other because the distance between them will increase by one after each iteration. So overall, the complexity is O(N - L + L) = O(N)
