LeetCode 141.环形链表 142.环形链表II
对题目不熟悉的同学，可以先刷下题，结合LeetCode上的题解和评论
前不久刷算法题，用快慢指针法求解141题判断链表是否有环。随后开始解142题，用了HashMap的解法，结果看评论区的大佬还是用双指针法来求解。大佬的解题分两个步骤
步骤一：使用快慢指针判断链表是否有环
步骤二：找到入环开始的节点
要完成步骤一很简单，步骤一就是141题的解法。这不是本篇文章要讲的内容。那么我们如何找到入环开始的节点呢？
引用@算法小菜 大佬的解题思路如下：
解题思路：分两个步骤，首先通过快慢指针的方法判断链表是否有环；接下来如果有环，则寻找入环的第一个节点。具体的方法为，首先假定链表起点到入环的第一个节点A的长度为a【未知】，到快慢指针相遇的节点B的长度为（a + b）【这个长度是已知的】。现在我们想知道a的值，注意到快指针p2始终是慢指针p走过长度的2倍，所以慢指针p从B继续走（a + b）又能回到B点，如果只走a个长度就能回到节点A。但是a的值是不知道的，解决思路是曲线救国，注意到起点到A的长度是a，那么可以用一个从起点开始的新指针q和从节点B开始的慢指针p同步走，相遇的地方必然是入环的第一个节点A。文字有点绕，画个图就一目了然了~~
看完了解题思路还是懵逼。然后这道题就被我搁置了半个月，今天看到公众号上有一篇文章上有找到入环开始的节点的内容，作者引入了很多个变量来解答s，a，b，n，r，L，X。
更懵了好吗？并且网上这样的文章很多，大家有兴趣可以去搜索一下。
废话不多说，现在开始讲解双指针法解题思路。先上图
我们直接跳过步骤一：使用快慢指针判断链表是否有环。讲解步骤二
定义
链表头结点到环入口的长度为：a
首次相遇的点到环入口的长度为：b
我们使用快慢指针求相遇的点，当快慢指针首次相遇时，得到如下公式
一：慢指针走过的路程为 a + b;
二：快指针走过的路程为 2a+2b；
推导
我们不再引入其余的变量来计算，现在开始推导
我们想象一下当快指针走过的路程为 2a+b时，停留在哪个位置（不考虑快指针一次走两步的问题）？
答案是快指针走过路程为2a+b时，停留在环入口的结点。
好的，那我们再想象一下，当快指针走过的路程为a+b时，停留的位置？这个就不用考虑了，慢指针在与快指针首次相遇时正好走过a+b的路程。
所以答案是快指针走过路程为a+b时，停留在首次相遇的结点。
由此，我们可以得出结论首次相遇的结点走a的距离可以到达环入口结点。（这里可能存在的a比环的长度更大的情况）
解题
要获取有环单向列表环入口的节点，只需要两个慢指针p1,p2分别从首次相遇的结点和链表头结点开始遍历。
p1从链表头结点走a步到达入环结点
p2从首次相遇的结点走a步到达入环结点
p1,p2必然在入环节点相遇
代码如下:
public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head, low = head; while (fast != null && fast.next != null) { fast = fast.next.next; low = low.next; if (fast == low) break; } if (fast == null || fast.next == null) return null; ListNode p1 = fast, p2 = head; while (p1 != p2) { p1 = p1.next; p2 = p2.next; } return p1;
}
写在最后的话
实际上@算法小菜 大佬要表达的就是这个意思，居然时隔半个月之后才懂。还是需要自己多思考!!
