浅谈双指针技巧（二）—通过双指针判断链表成环问题

• 2022 年 9 月 8 日
• 筆記
• JAVA, 算法与数据结构

在上一篇文章（//www.cnblogs.com/jilodream/p/16666435.html）中，我们已经知道可以通过快慢指针，最终判断一个单向链表是否成环。
一般在判断存在环之后，还有一个经典的问题：
查找环的起点节点是哪里呢
力扣 142. 环形链表 II （//leetcode.cn/problems/linked-list-cycle-ii/）
也就是查找到下图中的这个位置

乍一看这个问题很难处理，除非像前文说的通过缓存来判断首次加入到缓存中的节点外，并没有什么其他好的办法。

如果直觉不能给我答案，我们往往采用数学的办法：

如上图，假设判断有环后，慢指针执行的距离是N，则快指针的执行的距离是2N。他们相遇的点是meet点。我们可以理解2N-N，也就是快指针超过慢指针的距离，其实就是围绕meet节点绕了x圈（x>=0）。
所以最终的结论就是：

N=慢指针走的距离=快指针超过慢指针的距离=围绕meet节点走x圈

此时我们让两个指针（a、b）同时走上述的两个N，也就是一个从head节点，一个从meet节点开始，同速，一直走N步，最终会同时到达meet节点。
而这个过程的最后一部分，也就是start节点到meet节点，两者的路径其实是重合的。因此这两个指针（a、b）会首先在start节点相遇，然后同时走相同的一段路径，并最终一同走到meet节点。
如下图：

a指针移动距离=b指针移动距离=N-lastLen（lastLen表示从start节点到meet节点之间的最短距离+x*环的周长）

也就是：
a指针移动距离=b指针移动距离
所以我们在寻找环的起点start节点时，分为两部分：
1、通过快慢指针找到二者的相遇点meet节点。
2、新定义两个节点a、b，分别指向meet 节点和head节点。两者按照相同的速度前进，第一次相遇的节点就是环的起始节点start

我们直接看代码：

 1     public ListNode detectCycle(ListNode head) {
 2         ListNode tempHead = head;
 3         if (tempHead == null) {
 4             return null;
 5         }
 6         ListNode low = tempHead;
 7         ListNode fast = tempHead;
 8         while (true) {
 9             if (fast.next == null || fast.next.next == null) {
10                 return null;
11             }
12             fast = fast.next.next;
13             low = low.next;
14             if (fast == low) {
15                 break;
16             }
17         }
18         ListNode a = tempHead;
19         ListNode b = fast;
20         while (true) {
21             if (a == b) {
22                 break;
23             }
24             a = a.next;
25             b = b.next;
26         }
27         return a;
28     }