剑指offer JZ23 链表中环的入口结点

问题描述：

给定一个长度为n的链表，首先判断其是否有环，然后找到环的入口。

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

思路：

1. 投机一点的做法

从头遍历链表，如果有环，那么有些节点一定会被重复访问，那么只需返回第一个重复的节点即可。java中用set或者map都可以实现，并且方法是现成的，所以代码很简单。

代码实现：

public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead) {HashSet<ListNode> set = new HashSet<>();while (pHead != null) {if (set.contains(pHead)) {return pHead;}set.add(pHead);pHead = pHead.next;}return null;}
}

2.双指针（推荐掌握）

设置快慢指针。

分析问题，我们发现，这道题需解决两个问题，①判断链表是否有环；②在有环的链表中找到环的入口。

对于①：如果无环，那链表的最后一定是指向null，反之，则快慢指针会循环遍历环的部分，会相遇。

②：此时我们已经确定了链表有环，此时我们需要推导一下。我们让快指针fast每次前进两个节点，慢指针slow每次前进1个节点，fast先进入环，并在里面循环，随后slow进入环，最终两者会在环内某个节点处相遇。

如下图，我们假设fast在环内走了n圈，slow走了m圈，然后相遇，而进入环之前的距离为x，环入口到相遇位置的距离为y，相遇位置到环入口的另一段距离为z;那么在这个过程中，快指针一共走了x+n*(y+z)+y,慢指针共走了x+m*(y+z)+y，而相同的时间，fast是slow 速度的2倍，所以距离也是2倍，故：x+n*(y+z)+y=2(x+m*(y+z)+y),推导得出(其中N=n-2m，为一个整数)

$x + y =N*\left ( y+z \right )\Rightarrow x=N*\left ( y+z \right ) - y$

因为x+y是从头到相遇节点的长度，y+z是环的长度，由式子得出，进入环之前的距离x为一个整数倍的环的长度减去一个由入环节点到相遇节点的距离。也就是说，如果以相同的速度，让两个指针，一个从头开始遍历到相遇节点，一个从相遇节点在环中遍历，最后到相遇的节点走的是相同的距离，而因为此时速度相同，所以其中y这个距离，就是重复走的距离，那么他们第一次相遇的点就是环的入口节点了。

代码：

public class Solution {//先判断有没有环，有环则返回相遇的节点public ListNode hasCycle(ListNode pHead){if (pHead == null) return null;//快慢指针ListNode fast = pHead;ListNode slow = pHead;//若无环，则fast肯定先到链表尾while (fast != null && fast.next != null){//fast移动两步fast = fast.next.next;//slow移动一步slow = slow.next;//相遇，则表明有环，并返回相遇的位置if (fast == slow)return slow;}//无环return null;}public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode slow = hasCycle(pHead);//无环if (slow == null)return null;//有环，则快指针返回链表头ListNode fast = pHead;//再次相遇则为入口while (fast != slow){fast = fast.next;slow = slow.next;}return slow;}
}