题解 | #链表中环的入口结点#

/*
*首先用快慢指针判断链表中是否有环，然后借助环中一个节点，找到环的长度。
*再借助两个指针，第一个先移动环的长度，然后两个同步移动，两者相遇时既是环的起点。
*/
public static ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead==null){
return null;
}
ListNode p = pHead;
ListNode q = pHead;
ListNode meeting = MeetingNode(pHead);
if (meeting!=null){
ListNode temp = meeting.next;
int length = 1;
while (temp!=meeting){
length++;
temp =temp.next;
}
for (int i = 0; i < length; i++) {
p = p.next;
}
while (p!=q){
p = p.next;
q = q.next;
}
return p;
}
return null;
}
public static ListNode MeetingNode(ListNode pHead){
if (pHead==null){
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
while (fast!=null&&slow!=null){
slow = slow.next;
fast = fast.next;
if (fast!=null){
fast = fast.next;
}
if (slow==fast){
return slow;
}
}
return null;
}