链表中环的入口结点（题号23）

问题描述：

给一个长度为n的链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n）

解题思路：

1. hash法

   遍历所有节点，将节点地址依次存储在一个hash表中，等走完环形部分回到环的入口节点处，此时hash表中已经存储过所有节点，经过判断是否存在该节点会返回true，则该节点就是入口节点，直接返回即可。

   时间复杂度：O(n)

   空间复杂度：O(n)

   该方法因为空间复杂度不满足要求，所以不做重点讲解

2. 双指针法

   初始化两个节点指向链表头结点，一个步进快的fast，一个步进慢的slow，设定fast节点每次步进两步，slow节点每次步进一步。当两个节点第一次相遇（指向同一个节点，此时在环中）的时候，将其中一个节点重置为指向头结点然后分别以一为步长重新步进，待两个节点重新相遇，则被指向的节点就为环的入口节点。

   时间复杂度：O(n)

   空间复杂度：O(1)

   下面着重讲解该方法

注意事项：

跳出循环的判断条件以及跳出第一次循环后判断是否是正常跳出：正常跳出则返回null，表示没有环，打断则继续第二个循环

论证

• 结论一：两个节点第一次相遇一定指向环中的节点

  显然节点的步进速度一快一慢，这里的设定是快速节点是慢速节点速度的两倍，所以假如链表没有环，则慢速节点永远无法追上快速节点与其相遇，所以反推两节点能相遇必然链表中存在环并且相遇的节点只能在环中。

• 结论二：重置其中一个节点指向头结点后分别以一为步长重新步进，待两个节点重新相遇，则被指向的节点为环的入口节点

  image

  （图片内容仅用于抽象说明问题）

  如上图a：

  |ad|=a，|dg|=b，|gd|=c

  快指针路程=a+（b+c）k+b，k>=1，其中b+c为环的长度，k为环的圈数（k>=1，即最少一圈，不能是0圈，不然快慢指针走的路程一样，矛盾）。

  慢指针路程=a+b。

  因为快指针的路程是慢指针的路程的两倍，所以：（a+b）*2=a+（b+c）k+b。

  化简得：

  a=（k-1）（b+c）+c，这个式子的意思是：链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈数环长度。其中k>=1，所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

  该证明引用自：知乎

代码

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) {
                break;
            }
        }
        // 正常退出循环代表该链表无环，所以返回null
        if (fast == null || fast.next == null) {
            return null;
        }
        // 选择一个节点重置到链表头节点位置
        fast = pHead;
        // 分别重新以步长为一的速度步进直到两个节点重新相遇，终止循环
        while (fast != null && fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        // 返回相遇位置的节点即为环的入口
        return slow;
    }
}