链表环的入环节点
链表中环的入口结点
http://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
主要是 第一次相遇节点开始走D=(n-1)(s1+s2)+s1,,,,,,,n=1时,D=s1 ,所以从第一次相遇时,快指针已经绕了环一圈,而这时再从第一次相遇的节点开始,一个指针在链表头,一个指针在第一次相遇的节点,当这两个指针第一次相遇时的节点就是入环节点
可读代码:
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null){
return pHead;
}
ListNode p1=pHead;
ListNode p2=pHead;
ListNode p3=pHead;
boolean isHasCycle=false;
while(p1!=null&&p2.next!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){
isHasCycle=true;
break;
}
}
ListNode res=null;
if(isHasCycle){
while(p3!=null){
if(p1==p3){
res=p3;
break;
}
p3=p3.next;
p1=p1.next;
}
}
return res;
}