当前位置 博文首页 > 是琳琳呀!的博客:判断一个链表是否有回环返回第一个回环节点
定义一个快慢指针,快指针一次走两步,慢指针一次走一步,进入循环,此时结束循环有两种情况,一种是没有环,一种是当快慢指针相遇时,结束循环。因为快指针是慢指针的两倍,则当二指针相遇时快指针走了慢指针的两倍,设进入环时的路程为X,慢指针进入环后走了L,即当二人相遇时,快指针又走了X+2L的路程,则快指针在离入环点环还有X.
public Node theListNode(){
if(headnull){
return null;
}
Node fast=this.head;
Node slow=this.head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fastslow){
break;
}
}
if(fastnull||fast.nextnull) {
return null;
}
slow=this.head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}