141. 环形链表 - 题解与详细分析

题目描述

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

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

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

示例

示例 1：

text

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

示例 2：

text

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

示例 3：

text

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

解题思路

判断链表是否有环是一个经典的链表问题，最优雅的解决方案是使用快慢指针（Floyd's Cycle-Finding Algorithm）。

快慢指针原理

• 慢指针：每次移动一步

• 快指针：每次移动两步

如果链表中存在环，快指针最终会追上慢指针（两者相遇）；如果不存在环，快指针会先到达链表末尾（NULL）。

代码实现

c

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head;
struct ListNode *slow = head;

while(fast && fast->next)
{
slow = slow->next; // 慢指针移动一步
fast = fast->next->next; // 快指针移动两步

if(slow == fast) // 如果相遇，说明有环
return true;
}

return false; // 快指针到达末尾，说明无环
}

代码详解

核心逻辑

c

while(fast && fast->next)
{
slow = slow->next; // 慢指针移动一步
fast = fast->next->next; // 快指针移动两步

if(slow == fast) // 检查是否相遇
return true;
}

循环条件分析：

• fast：确保快指针本身不为空

• fast->next：确保快指针可以安全地移动两步

执行过程可视化

有环的情况（示例1）：

text

链表：3 -> 2 -> 0 -> -4 -> 2（形成环）

初始：slow -> 3, fast -> 3

第1次循环：
slow -> 2, fast -> 0
比较：2 != 0

第2次循环：
slow -> 0, fast -> 2
比较：0 != 2

第3次循环：
slow -> -4, fast -> -4
比较：-4 == -4 → 返回true

无环的情况：

text

链表：1 -> 2 -> 3 -> 4 -> NULL

初始：slow -> 1, fast -> 1

第1次循环：
slow -> 2, fast -> 3
比较：2 != 3

第2次循环：
slow -> 3, fast -> NULL
条件判断：fast == NULL → 退出循环，返回false

为什么快慢指针有效？

数学证明

假设链表环外部分长度为 L，环的周长为 C。

当慢指针进入环时：

• 慢指针位置：0（环的起点）

• 快指针位置：L % C（因为快指针已经走了 2L 步）

快指针相对于慢指针的速度是 1 步/单位时间（快指针比慢指针快一步），所以快指针需要追赶的距离最多为 C-1 步。

因此，在 C-1 次循环内，快指针一定会追上慢指针。

时间复杂度分析

• 慢指针最多走 L + C 步（环外长度 + 环周长）

• 快指针最多走 2(L + C) 步

• 时间复杂度：O(n)，其中 n 是链表长度

其他解法

方法二：哈希表法

c

#include <stdbool.h>

bool hasCycle(struct ListNode *head) {
struct ListNode *visited[10000] = {0}; // 简单的哈希表
int count = 0;

struct ListNode *current = head;
while (current != NULL) {
// 检查当前节点是否已经访问过
for (int i = 0; i < count; i++) {
if (visited[i] == current) {
return true;
}
}

// 记录已访问的节点
visited[count++] = current;
current = current->next;
}

return false;
}

优缺点：

• 优点：思路简单直观

• 缺点：空间复杂度 O(n)，需要存储所有访问过的节点

方法三：标记法（修改节点值）

c

bool hasCycle(struct ListNode *head) {
struct ListNode *current = head;

while (current != NULL) {
// 如果遇到特殊标记值，说明有环
if (current->val == 1000000) {
return true;
}

// 标记当前节点（假设节点值不会等于1000000）
current->val = 1000000;
current = current->next;
}

return false;
}

优缺点：

• 优点：空间复杂度 O(1)

• 缺点：修改了原始链表数据，不推荐在实际中使用

复杂度分析

快慢指针法

• 时间复杂度：O(n)，最坏情况下需要遍历整个链表

• 空间复杂度：O(1)，只使用两个指针变量

哈希表法

• 时间复杂度：O(n)，需要遍历链表

• 空间复杂度：O(n)，需要存储所有访问过的节点

扩展问题

如果要求找到环的入口节点

c

struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow = head;
struct ListNode *fast = head;

// 第一阶段：判断是否有环
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) {
// 第二阶段：找到环的入口
struct ListNode *ptr1 = head;
struct ListNode *ptr2 = slow;

while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

return ptr1; // 环的入口节点
}
}

return NULL; // 无环
}

原理：

应用场景

快慢指针技巧在很多场景中都有应用：

总结

判断链表是否有环是一个经典的链表问题，快慢指针法是最优解：

掌握快慢指针技巧对于解决链表相关问题非常有帮助，这是面试中常见的考点之一。