环形链表 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

想象兔子和乌龟在同一跑道上，一个速度快、另一个速度慢。如果跑道有环，兔子必然在一段时间后追上乌龟。对于链表来说，如果在链表中引入两个以不同速度（一个比另一个快一倍）前进的指针，在链表存在环的情况下，这两个指针必定会相遇。

视频讲解：【基础算法精讲 07】，制作不易，欢迎点赞！

⚠注意：代码比较两个节点的时候，比较的是内存地址是否一致，并没有比较节点的 val。

答疑

问：兔子会不会「跳过」乌龟，从来不会和乌龟相遇呢？

答：这是不可能的。如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。

问：为什么代码的 $while$ 循环没有判断 $slow$ 是否为空？

答： $slow$ 在 $fast$ 后面，如果 $fast$ 不是空，那么 $slow$ 也肯定不是空。好比快人先去探路，慢人走的都是快人走过的路。

Python 解法1C++ 解法1

python

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head; // 乌龟和兔子同时从起点出发
        while (fast && fast->next) {
            slow = slow->next; // 乌龟走一步
            fast = fast->next->next; // 兔子走两步
            if (fast == slow) { // 兔子追上乌龟（套圈），说明有环
                return true;
            }
        }
        return false; // 访问到了链表末尾，无环
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。理由见本题视频讲解【基础算法精讲 07】。
空间复杂度： $O (1)$ 。

进阶题目

返回入环口。见 142. 环形链表 II。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

答疑 ​

复杂度分析 ​

进阶题目 ​

分类题单 ​

答疑

复杂度分析

进阶题目

分类题单