Start of Circle
出处
Solution
寻找某个特定位置,用runner和chaser。这里的技巧是,如果runner以两倍速度前进,chaser以一倍速前进,在有环的情况下,runner与chaser一定能在某点相遇。相遇后,再让chaser从头节点出发再次追赶runner,此时两者都以一倍速前进,可以证明,第二次相遇的节点即为环的开始位置。
Complexity
时间复杂度 O(n)
Code
Node startCircle(Node head){
if (head == null) return null;
Node quick = head;
Node slow = head;
Node backup = head;
while (quick != null && quick.next != null){
quick = quick.next.next;
slow = slow.next;
if (slow == quick)
break;
}
if (quick == null || quick.next == null){
return null;
}
slow = backup;
while (slow != quick){
slow = slow.next;
quick = quick.next;
}
return slow;
}