142. 环形链表 II [medium]

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

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

为了表示给定链表中的环，我们使用整数 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
解释：链表中没有环。

进阶：

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

通过次数91,331 | 提交次数179,685

Third Try

2020-10-09

要不是之前做过，真是不知道怎样才能在空间为O(1)的情况下搞定这道题。就算做过，写出来 a + b + c = 2 * (a + c)这式子，也差点不知道如何推导出a点。

另外在写while语句让head和collision相遇的时候，也差点写成了死循环，因为其实一开始是在head之前起步，而collision也是新的起步的点，因此应该是head对比collision的下一个点才行。

其实这时候重新返回看first try里的解法，虽然空间复杂度是O(n),但是非常可靠。这种在套路化训练之前摸索出来的方法，充满了直接的工程暴力美感。

# 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:
        """
        环节点为a, 环长度为b, 相遇点为c
        首先两倍走
        a + b + c = 2 * (a + c)
        b = a + c 
        a = b - c
        从起点出发，走a长度的时候，会跟从c出发的撞到一起。
        要不是做过这题目，真是又想不起来了
        """  
        if not head:
            return None 
        fastnode = head.next 
        node = head
        collision = None  
        while node and fastnode and fastnode.next:
            if node == fastnode:
                collision = node 
                break 
            node = node.next 
            fastnode = fastnode.next.next 
        if not collision:
            return None 
        
        collision = collision.next  # 起点是下一个，因为一开始的起点其实是在head之前
        while head and collision:
            if head == collision:
                return head  
            head = head.next 
            collision = collision.next 

Second Try

2020-07-07

参考题目里的评论，非常容易理解:

by @flyFatSeal https://leetcode-cn.com/problems/linked-list-cycle-ii/comments/52525

     7<-6<- 5
      |     ^
      |     |
0->1->2->3->4
[-----]
   a

如上图所示,我们设置快慢两个指针，fast, slow fast一次前进两步，slow一次前进一步，如果存在环则必然会相遇。

设a为第一个节点到入环节点的距离。 a=[0->2]
设b为入环口到相遇点的距离。b=[2->6]
设c为相遇点到入环口的距离。c=[6->2]
当fast，和slow相遇的时候，fast经过的节点是slow的两倍，设slow经过的节点数为S。
根据上面的设置，可知 S=a+b ,2S=a+b+c+b，可知 a=c
此时让slow回到第一个节点， fast处于第一次相遇的节点，此时slow从第一个节点出发，因为a=c，所以fast，和slow会在入环口第二次相遇，得到要求的节点。

另外个人再补充如果fast指针已经走了多次循环的情况：

有循环不影响结论。
假设循环为n, 那么s = a + b, 2s = a + b + c + b + n (b + c) ==> c + n (b + c) = a ==> 一个从起点出发，一个从b点出发，当从起点的出发到a的时候，另一个指针也走了 c + n * (b+c)的长度，刚好也到a点。

其次需要注意的点是起点的确认。比如根据推导a=c,而且第二次出发是从相遇点开始出发，所以第一次的时候需要注意两个从head一起出发，而不是从head的前一步，或者后一步出发, 否则a和c的长度就混乱了。

因此第一次nodei = head.next, nodeii = head.next.next，如果写成nodei = head, nodeii = head.next虽然也能判断出循环，但是要找到循环交汇点就麻烦了，容易陷入无限循环。

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

# O(1)空间版本，不想推导了
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # 一波先判断到底
        if not (head and head.next and head.next.next):
            return None 

        # 重点在于起点需要选择好
        # 由于推导的时候是从head作为起点开始出发， 在遇到相遇点的时候，第二轮就是从相遇点开始走起的，因此也需要模拟出第一步从head凑出一步和两步的效果
        # 如果一开始写成nodei = head, nodeii = head.next，则结果错误
        # 无尽循环bug写法,依然可以找到环，但是在第二波循环的写法里直接进入无限循环了，因为每一次都只前进一步，起点错误就永远追不上
        # nodei = head 
        # nodeii = head.next 
        nodei = head.next 
        nodeii = head.next.next
        # 如果不是前面直接判断了一波head.next.next，nodeii为None的情况就往下走了，贡献了一波错误提交
        while nodeii:
            if nodei == nodeii:
                break 
            if nodeii.next and nodeii.next.next:
                nodei = nodei.next 
                nodeii = nodeii.next.next 
            else:
                return None
         
        # print("catcha")
        nodei = head 
        while True:
            if nodei == nodeii:
                return nodei 
            nodei = nodei.next 
            nodeii = nodeii.next 

执行用时：52 ms, 在所有 Python 提交中击败了27.51%的用户
内存消耗：19 MB, 在所有 Python 提交中击败了6.25%的用户

First Try

2020-07-07

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 感觉用快慢指针也找不出来在哪里汇合啊？
        cache = dict()
        i = 0
        while head:
            if head in cache:
                return head 
            cache[head] = i 
            head = head.next 
            i += 1
        return None 

执行用时：40 ms, 在所有 Python 提交中击败了79.69%的用户
内存消耗：20 MB, 在所有 Python 提交中击败了6.25%的用户