【每日一题】- 2020-01-14 - 142. 环形链表 II

[azl397985856]

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

说明：不允许修改给定的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：
你是否可以不用额外空间解决此题？

[unclegem]

假设从链表开始的位置到环入口的距离为p，慢指针在环内走了的距离为c，假设慢指针一共走了n步，快指针一共做了2n步。
那么，有p+c=n
显然，从p+c这一点开始，慢指针再走n步，必然还会回到这个点。为啥？【因为经过了2n步，快指针到达了这一点，所以慢指针如果再走n步，也会到达这一点】
如果让快指针从链表头开始走n步，也会到达p+c这个位置，二者相遇的第一个地方，肯定是环入口。

    public ListNode detectCycle(ListNode head) {
    
        ListNode slow = head, fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                
                ListNode slow2 = head;
                while(slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                
                return slow;         
            }           
        }

        return null; 
    }

    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow

[azl397985856]

Two Pointer(Python Code)

• x means the first meeting point

• assume L is the length between the start point and the entry point of the loop.

• and C is the length between the entry point and x

• and D is the remaining part of the circle.

2(L + C) is the distance which fast traveled, and so does L + 2C + D

So we setup two pointers which steps range from one to two. when the two pointers meets, slow point starts from start point again, fast point continue. Absolutely, we can meet at the entry point, because L = D

That's all!

#
# @lc app=leetcode.cn id=142 lang=python3
#
# [142] 环形链表 II
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        x = None

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                x = fast
                break
        if not x:
            return None
        slow = head
        while slow != x:
            slow = slow.next
            x = x.next
        return slow

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[xushimin]

显然，从p+c这一点开始，慢指针再走n步，必然还会回到这个点。为啥？【因为经过了2n步，快指针到达了这一点，所以慢指针如果再走n步，也会到达这一点】
这个推理完全没有看懂，查阅了资料，这个是Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)；所以你上面的解释相当于去证明Floyd判圈算法有效性？

[jincdream]

显然，从p+c这一点开始，慢指针再走n步，必然还会回到这个点。为啥？【因为经过了2n步，快指针到达了这一点，所以慢指针如果再走n步，也会到达这一点】 这个推理完全没有看懂，查阅了资料，这个是Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)；所以你上面的解释相当于去证明Floyd判圈算法有效性？

上面的解法只是基于这个结论做的实现。推理这个结论的过程如果看不懂，可以看我这个试试理解。

假设橙色部分距离为A， 蓝色为B， 绿色为C，相遇点为X，快指针2n，慢指针n, 环距离 v

那么有在相遇时有，

A + B + C + B - A = A + B
A = C

所以在快慢指针用同样的速度 1 ，一个在原点，一个在相遇点继续走的时候，必然在入口相遇。

[cherie-wuyajun]

这是来自QQ邮箱的自动回复邮件。您好，邮件已收到，我将会尽快给您回复。

[fyyzkd]

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。

[xiaosisong]

我已经收到了，会尽快查看的，谢谢

[peak-up-fsl]

已收到，谢谢，我会尽快回复。