VietMX Staff asked 3 years ago
You can make use of Floyd’s cycle-finding algorithm, also known as tortoise and hare algorithm.
The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.
- If the linked list has a loop they will definitely meet.
- Else either of the two references(or their
next) will becomenull.
Complexity Analysis
We only use two nodes (slow and fast) so the space complexity is O(1).
Implementation
boolean hasLoop(Node first) {
Node slow = first;
Node fast = first;
while (fast != null && fast.next != null) {
slow = slow.next; // 1 hop
fast = fast.next.next; // 2 hops
if (slow == fast) // fast caught up to slow, so there is a loop
return true;
}
return false; // fast reached null, so the list terminates
}