题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路

1. 首先要确定这个链表中包含环。

2. 然后找到环的长度，根据环的长度找到环的入口节点。

先上结论，然后再证明：

• 结论1：设置快慢指针，快指针每次走一步，慢指针每次走两步，假如链表中有环，它们一定在环中相遇。
• 结论2：假设环的长度是n，先让快指针走n步，然后快慢指针一起出发，每次一起走一步，最后一定相遇于环的入口节点。

解决这个问题可以分三步。

（1）第一步是确定一个链表中是否包含环。我们可以用两个指针来解决这个问题。定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；吐过走得快得快的指针走到了链表的末尾（ListNode的next指向null）都没有追上第一个指针，那么链表就不包含环。

（2）第二步是找到环中节点的数目，这一步的目的就是为寻找环的入口做铺垫。我们在上面提到判断一个链表里面是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数K （环的长度）。

（3）第三步是找到环的入口。我们还可以利用两个指针来解决这个问题。 转换为求环的倒数第N-K个节点.   先定义两个指针P1和P2指向链表的头结点。如果链表中的环有K个节点，则指针P1先在链表上向前移动K步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点(其实是链表的尾部)。

public ListNode EntryNodeOfLoop(ListNode head) {
    // 当头结点为空或只有一个头结点时，一定没有环
    if (head == null || head.next == null)
        return null;
    ListNode low = head, fast = head;
    int cycleLength = 1;
    while (low != null && fast != null) {
        low = low.next;
        fast = fast.next.next;
        // 根据结论1，如果low和fast相遇，则链表中一定有环，可以顺便计算环的长度
        if (low == fast) {
            fast = fast.next;
            while (low != fast) {
                fast = fast.next;
                cycleLength++;
            }
            break;
        }
    }
    // 如果链表没有环，则low或fast指针到达链表末尾，为空
    if (low == null || fast == null)
        return null;
    // 重置low和fast指针，根据结论2寻找环的入口节点
    low = head; fast = head;
    while (cycleLength-- > 0)
        fast = fast.next;
    while (low != fast) {
        low = low.next;
        fast = fast.next;
    }
    return low;
}