题解 | #链表中环的入口结点#
链表中环的入口结点
http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
首先定义两个指针，从指向 head 节点，快指针每次走两步，慢指针每次走一步，如果存在环，则快指针入环后，则每走一步快指针就会距离慢指针更近一步，那么总会有一时刻，快指针会追上慢指针，则此时可判定链表有环，于此同时，定义第三个节点从head开始，步长与慢指针相同，则慢指针与新指针相遇处即为环的入口，相关证明参考：https://zhuanlan.zhihu.com/p/33663488
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode fast = pHead;
ListNode slow = pHead;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
//如果二者相遇，则说明存在环
if (fast == slow) {
ListNode slow2 = pHead;
while (fast != slow2) {
fast = fast.next;
slow2 = slow2.next;
}
return slow2;
}
}
return null;
}
}
