141. 环形链表

力扣题目链接 (opens new window)

题目描述

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则该链表中没有环。

注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true；否则，返回 false。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个有效索引

思路

最直观的做法，是用哈希表记录访问过的节点。如果再次访问到同一个节点，说明链表有环。

这种方法可以通过本题，但需要 O(n) 的额外空间。有没有只使用常量空间的办法呢？

那么就应该想到快慢指针了：

• slow 每次走一个节点；
• fast 每次走两个节点；
• 如果链表无环，fast 会先走到链表末尾；
• 如果链表有环，fast 和 slow 最终一定会在环内相遇。

很多录友能记住这个结论，但为什么有环就一定会相遇，而不是一直错开呢？

首先，fast 走得更快，所以它一定比 slow 先进入环。等两个指针都进入环后，可以把这个过程想象成在环形跑道上追赶。

每轮移动，fast 走两步，slow 走一步。相对于 slow 来说，fast 每轮只向前靠近一个节点。

也就是说，两个指针在环上的距离每轮都会缩短一格，不会跳过彼此。因此只要链表有环，它们就一定会在某个节点重合。

注意循环条件必须写成 fast != nullptr && fast->next != nullptr。因为 fast 每次要走两步，访问 fast->next->next 之前，必须先保证 fast 和 fast->next 都不为空。

模拟过程

以 head = [3,2,0,-4]，pos = 1 为例，链表尾节点 -4 指向节点 2：

1. 开始时，slow 和 fast 都指向头节点 3。
2. 第一轮移动后，slow 指向 2，fast 指向 0。
3. 第二轮移动后，slow 指向 0，fast 绕过链表尾部后指向 2。
4. 第三轮移动后，slow 和 fast 都指向 -4。
5. 两个指针指向同一个节点，因此链表中存在环，返回 true。

整个追赶过程如下：

如果链表没有环，fast 最终会指向空节点，或者 fast->next 为空，此时退出循环并返回 false。

解题代码

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // fast 每次走两步，所以还要判断 fast->next 是否为空
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) { // 相遇说明链表中存在环
                return true;
            }
        }

        return false;
    }
};

复杂度分析

• 时间复杂度：O(n)。无环时最多遍历链表一次；有环时，快慢指针会在有限轮移动后相遇。
• 空间复杂度：O(1)。只使用了两个指针。

其他语言

Python3

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:  # 比较节点本身，而不是节点值
                return True

        return False

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) { // 相遇说明链表中存在环
                return true;
            }
        }

        return false;
    }
}

Go

func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast { // 相遇说明链表中存在环
            return true
        }
    }

    return false
}

JS

var hasCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) { // 相遇说明链表中存在环
            return true;
        }
    }

    return false;
};

与代码随想录联系

本题是快慢指针在链表中的经典应用。代码随想录的环形链表也讲解了为什么两个指针一定会相遇。

做完本题，建议继续做142. 环形链表 II。本题只判断有没有环，142 题还要通过数学推导找到环的入口，是对快慢指针更进一步的运用。