【leetcode】Q142 环形链表II

[0xbitboy]

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

      // 快慢指针，如果最终能碰到一起则说明有环
        // 1. 设 head 到 环的起点的 距离为a
        // 2. 设 环的长度为b
        // 3. 设当slow和fast第一次相遇时，slow 走的距离为 a+x, 则 faster走的是2*(a+x)
        // 4. 当fast 和 slow相遇时，说明faster 至少走了1圈了，设fast 走了m圈
        // 5. fast 走的距离为 a + mb + x
        // 6. slow 走的距离为 a + x
        // 7. 因为 fast 走的速度是 slow的2倍，故，2* (a + x) = a + mb +x,  化简可得，a = mb -x,  x = mb -a;
        // 8. 假设 fast再走 a步，则 fast走的距离为 2a + mb + x, 由7可得， x=mb-a, 故，2a + mb + x = a + 2mb; 说明，fast刚好走了2m环，此时正是 环起点。
        // 9. 由8的性质，我们可以在快慢指针第一次相遇后，再设置一个新的指针再头节点开始 跟 fast 以1倍的速度走。 那么 当两个指针相遇时，说明新指针刚好走到了环的起点。