链表环的入环节点
链表中环的入口结点
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; }