[Leetcode][python]Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II

雨点打透心脏的1/2处 2022-06-04 01:59 152阅读 0赞

# Linked List Cycle #

## 题目大意 ##

判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？

## 解题思路 ##

哈希表

快慢指针

## 代码 ##

### 方法一：哈希表 ###

思路

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

算法

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

### 双指针 ###

通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

class Solution(object):
        def hasCycle(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True
            return False

# Linked List Cycle II #

## 题目大意 ##

如果给定的单向链表中存在环，则返回环起始的位置，否则返回为空。最好不要申请额外的空间。

## 解题思路 ##

详见：  
[https://shenjie1993.gitbooks.io/leetcode-python/142%20Linked%20List%20Cycle%20II.html][https_shenjie1993.gitbooks.io_leetcode-python_142_20Linked_20List_20Cycle_20II.html]

在Linked List Cycle中，我们通过双指针方法来判断链表中是否存在环。在此基础上，我们来找出环的起始节点。如下图所示，假设链表的起始节点为A，环的起始节点为B，快慢指针在C处相遇。因为快指针的速度是慢指针的两倍，所以在相同时间内，它走过的路程是慢指针的两倍，而快指针走过的路程是(x+y+z+y)，而慢指针走过的路程是(x+y)，根据关系我们可以得到x+y+z+y = 2(x+y)，也就是说x=z。此时快慢指针在C处，头指针在A处，而它们到B的距离相等，那么只要有两个指针分别从点A和点C出以相同的速度前进就会在点B处相遇，也就是找到了环的起始节点。

> 注：上面的情况是理想情况，实际上在点C相遇时，快指针可能已经绕着环走了好几圈了，如AB很长，而环很小的情况。假设走了n圈，此时等式为x+y+n(z+y) = 2(x+y)，即x=(n-1)(y+z)+z，而从点C绕n-1圈后再走z的距离还是会跟从点A出发的指针在点B相遇。

![这里写图片描述][70]

## 代码 ##

class Solution(object):
        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 slow == fast:
                    node = head
                    while node != slow:  # 到达C点新指针node从head开始走，速度和slow一样，最后会走到b点
                        node = node.next
                        slow = slow.next
                    return node
            return None

# 总结 #

思路题

[https_shenjie1993.gitbooks.io_leetcode-python_142_20Linked_20List_20Cycle_20II.html]: https://shenjie1993.gitbooks.io/leetcode-python/142%20Linked%20List%20Cycle%20II.html
[70]: /images/20220604/2bbd27f4db4843c6abda78b42c180d23.png