江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第141题：环形链表

给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返

题目描述

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1图片

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

示例 2：

示例2图片

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

示例 3：

示例3图片

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

提示

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

解题思路

方法一：快慢指针（Floyd 判圈算法）

这道题要求判断链表中是否存在环。我们可以使用快慢指针（也称为龟兔赛跑算法或 Floyd 判圈算法）来解决这个问题。

关键点：

  • 使用两个指针，一个慢指针（每次移动一步）和一个快指针（每次移动两步）
  • 如果链表中存在环，快指针最终会追上慢指针
  • 如果链表中不存在环，快指针会先到达链表尾部（即 null）

具体步骤：

  1. 初始化慢指针 slow 和快指针 fast，均指向链表头节点
  2. 循环移动指针，直到快指针到达链表尾部或者快慢指针相遇：
    • 慢指针每次移动一步：slow = slow.next
    • 快指针每次移动两步：fast = fast.next.next
  3. 如果快指针到达链表尾部（即 fast 为 null 或 fast.next 为 null），则链表中不存在环，返回 false
  4. 如果快慢指针相遇（即 slow == fast），则链表中存在环，返回 true

时间复杂度：O(n)，其中 n 是链表中的节点数。在最坏情况下，我们需要遍历整个链表。 空间复杂度：O(1)，只需要两个指针，不需要额外的空间。

方法二：哈希表

另一种解决方案是使用哈希表来记录已经访问过的节点。

关键点：

  • 使用哈希表记录已经访问过的节点
  • 如果当前节点已经在哈希表中，则链表中存在环
  • 如果遍历到链表尾部（即 null），则链表中不存在环

具体步骤：

  1. 创建一个哈希表，用于存储已经访问过的节点
  2. 遍历链表，对于每个节点：
    • 如果当前节点为 null，则链表中不存在环，返回 false
    • 如果当前节点已经在哈希表中，则链表中存在环，返回 true
    • 否则，将当前节点加入哈希表，继续遍历下一个节点

时间复杂度：O(n)，其中 n 是链表中的节点数。在最坏情况下，我们需要遍历整个链表。 空间复杂度：O(n)，需要使用哈希表存储已经访问过的节点。

图解思路

快慢指针分析表

以示例1为例：head = [3,2,0,-4], pos = 1

步骤 slow 位置 fast 位置 说明
初始状态 3 3 慢指针和快指针均指向头节点
第1步 2 0 慢指针移动一步，快指针移动两步
第2步 0 -4 慢指针移动一步，快指针移动两步
第3步 -4 2 慢指针移动一步，快指针移动两步（经过环）
第4步 2 -4 慢指针移动一步，快指针移动两步
第5步 0 0 慢指针移动一步，快指针移动两步，两者相遇

由于快慢指针相遇，因此链表中存在环，返回 true。

哈希表分析表

以示例1为例：head = [3,2,0,-4], pos = 1

步骤 当前节点 哈希表 操作 结果
初始状态 3 {} 将节点3加入哈希表 {3}
第1步 2 {3} 将节点2加入哈希表 {3, 2}
第2步 0 {3, 2} 将节点0加入哈希表 {3, 2, 0}
第3步 -4 {3, 2, 0} 将节点-4加入哈希表 {3, 2, 0, -4}
第4步 2 {3, 2, 0, -4} 节点2已在哈希表中 存在环

由于节点2已经在哈希表中，因此链表中存在环，返回 true。

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        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;
    }
}

Python 实现

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
        
        return False

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
};

执行结果

C# 实现

  • 执行用时：88 ms
  • 内存消耗：41.1 MB

Python 实现

  • 执行用时：48 ms
  • 内存消耗：19.8 MB

C++ 实现

  • 执行用时：8 ms
  • 内存消耗：8.0 MB

性能对比

语言 执行用时 内存消耗 特点
C# 88 ms 41.1 MB 执行速度适中，内存消耗较高
Python 48 ms 19.8 MB 执行速度适中，内存消耗适中
C++ 8 ms 8.0 MB 执行速度最快，内存消耗最低

代码亮点

  1. 🎯 使用快慢指针算法，空间复杂度为O(1)
  2. 💡 提前处理边界情况，避免空指针异常
  3. 🔍 代码简洁高效，逻辑清晰
  4. 🎨 适用于各种编程语言，通用性强

常见错误分析

  1. 🚫 没有处理链表为空或只有一个节点的边界情况
  2. 🚫 快指针移动时没有检查 fast.next 是否为 null，可能导致空指针异常
  3. 🚫 循环条件设置不正确，导致无法正确判断环的存在
  4. 🚫 使用哈希表方法时，没有正确比较节点的引用，而是比较节点的值

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
快慢指针 O(n) O(1) 空间复杂度低，实现简单 无法确定环的入口位置
哈希表 O(n) O(n) 实现简单，可以找到环的入口位置 空间复杂度高
标记法 O(n) O(1) 空间复杂度低 需要修改原链表结构

相关题目