Linked List Cycle
To decide if a singly linked list has a cycle and find the start node of cycle is such
and classical problem. Computer scientist spent some years before find this standard solution.
Like many other problems concerns about linked list, in this problem we also need to pointer:
a fastRunner
and a slowRunner
. The fastRunner
moves two steps every time while slowRunner
moves one.
At last either the two pointers are pointing the same node, or the fastRunner
meets the end of
the list. In the former case, there must be a cycle in the list. In the latter case, there are no cycle.
To find the start node, after the two pointers meets, we move slowRunner
back to the head
and moves
two pointer one step every time in parallel until they meet again. The node they meet at is the start point
of cycle.
Note at first both pointers point to head
, at this time we cannot say they meet and we must wait
for the second time they are both pointing to a same node.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class LinkedListCycle {
public ListNode detectCycle(ListNode head) {
ListNode fastRunner = head, slowRunner = head;
while (fastRunner != null && fastRunner.next != null) {
fastRunner = fastRunner.next.next;
slowRunner = slowRunner.next;
if (fastRunner == slowRunner) {
// find a cycle
slowRunner = head;
while (slowRunner != fastRunner) {
slowRunner = slowRunner.next;
fastRunner = fastRunner.next;
}
return slowRunner;
}
}
return null;
}
}