【java】链表:找到成环的起始节点
分析:
定义快慢双指针,在上一篇博客中,分析过若有环,快慢指针一定会相遇。
在这里,想要找到成环的起始节点,我们在快慢指针相遇的时候,让其中一个指针回到开始结点,然后两个指针一步一步走 ,再次相遇时那个节点就是起始节点。
(星星的位置是假定两指针相遇的位置)
求解:x=(n-1)(y+z)+z
public int cirCle() {
Node fast =head;
Node slow=head;
while((fast!=null)&&(fast.next!=null)) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow) {
fast=head;
while(fast!=slow) {
fast=fast.next;
slow=slow.next;
}
return slow.data;
}
}
return -1;
}