VietMX Staff asked 3 years ago
This is Floyd’s algorithm for cycle detection. Once you’ve found a node that’s part of a cycle, how does one find the start of the cycle?
- In the first part of Floyd’s algorithm, the hare moves two steps for every step of the tortoise. If the tortoise and hare ever meet, there is a cycle, and the meeting point is part of the cycle, but not necessarily the first node in the cycle.
- Once tortoise and hare meet, let’s put tortoise back to the beginning of the list and keep hare where they met (which is k steps away from the cycle beginning). The hypothesis (see math explanation) is that if we let them move at the same speed (1 step for both), the first time they ever meet again will be the cycle beginning.
Another solution to mention is Hash Map:
- Traverse the nodes list.
- For each node encountered, add it to the identity hash map
- If the node already existed in the identity map then the list has a circular link and the node which was prior to this conflict is known (either check before moving or keep the “last node”)
Implementation
public ListNode getLoopStartingPoint(ListNode head) {
boolean isLoopExists = false;
ListNode slowPtr = head, fastPtr = head;
while (!Objects.isNull(fastPtr) && !Objects.isNull(fastPtr.getNext())) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext().getNext();
if (slowPtr == fastPtr) {
isLoopExists = true;
break;
}
}
if (!isLoopExists) return null;
slowPtr = head;
while (slowPtr != fastPtr) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext();
}
return slowPtr;
}