[LeetCode] 142. Linked List Cycle II

[grandyang]

 

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

 

Follow up:
Can you solve it without using extra space?

 

这个求单链表中的环的起始点是之前那个判断单链表中是否有环的延伸，可参之前那道 Linked List Cycle。这里还是要设快慢指针，不过这次要记录两个指针相遇的位置，当两个指针相遇了后，让其中一个指针从链表头开始，一步两步，一步一步似爪牙，似魔鬼的步伐。。。哈哈，打住打住。。。此时再相遇的位置就是链表中环的起始位置，为啥是这样呢，这里直接贴上热心网友「飞鸟想飞」的解释哈，因为快指针每次走2，慢指针每次走1，快指针走的距离是慢指针的两倍。而快指针又比慢指针多走了一圈。所以 head 到环的起点+环的起点到他们相遇的点的距离 与 环一圈的距离相等。现在重新开始，head 运行到环起点 和 相遇点到环起点 的距离也是相等的，相当于他们同时减掉了 环的起点到他们相遇的点的距离。代码如下：

 

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }
        if (!fast || !fast->next) return NULL;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

 

讨论：单链表中的环的问题还有许多扩展，比如求环的长度，或者是如何解除环等等，可参见网上大神的这个总结贴。

 

Github 同步地址：

#142

 

类似题目：

Linked List Cycle

Find the Duplicate Number

 

参考资料：

https://leetcode.com/problems/linked-list-cycle-ii/

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[baicaihenxiao]

证明：

a                b         c              d
|________x_______|____y____|______z_______|

如图，假设都从a点出发，在c点相遇，bd为环，即要求ab的距离x。假设在c点相遇时，快指针已经转了m圈，慢指针已经转了n圈
$$
x + m(y + z) + y = 2(x + n(y + z) + y) \

=> x + y = (m - 2n)(y + z) \

=> x = (m - 2n)(y + z) - y + z -z \

=> x = (m - 2n - 1)(y + z) + z \

=> z = (2n + 1 - m)(y + z) + x \
$$

对$(2n + 1 - m)$的取值分3种情况讨论：

情况1：$(2n + 1 - m) \geq 2$

取最小值2，则有$z = 2y + 2z + x$，x y z均为非负数，说明x y z均为0，不存在这种情况，abcd为同一个点，即链表只有一个节点，且该节点的next指向自身。怎么做返回的节点都是入口。

情况2：$(2n + 1 - m) = 1$

有$z = y + z + x$，x y z均为非负数，说明x和y均为0，即整个链表都在环里，第一个节点即为入口(a b c为同一个点，即头结点)。快慢指针会在头结点相遇，再出发时在头结点就相遇了，即为入口。

情况3：$(2n + 1 - m) \leq 0$

$(2n + 1 - m)$只能为非正数，即$x \geq z$，且$(x-z)$为环的倍数。所以两个指针分别从a点和c点出发时，会在b点相遇，即为入口。

综上，情况1、2、3用这种方法均可找到入口。

GitHub没有tex渲染，可以看：

https://www.cser.club/leetcode/#/leetcode/142.LinkedListCycleII