力扣第141题：环形链表 C语言解法

题目描述

给定一个链表，判断链表中是否有环。

示例 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 \leq Node.val \leq 10^5$
pos 的值为 $- 1$ 或者链表中某个节点的索引（从 0 开始）。

解题思路

1. 问题分析

我们的目标是判断链表中是否存在环。环的存在意味着链表中某个节点的 next 指针指向了链表中的某个先前的节点，形成了一个循环。
若链表无环，则最后一个节点的 next 指针为 NULL。
直接遍历链表，若某个节点的 next 指针指向了之前访问过的节点，则说明存在环。

2. 快慢指针法

快慢指针（也称为 Floyd 判圈算法）是一种经典的解决环形链表问题的方法。它使用两个指针，分别以不同速度遍历链表：
- 慢指针每次走一步。
- 快指针每次走两步。
如果链表中存在环，快慢指针最终会在环内相遇。如果链表无环，快指针会走到链表的末尾（NULL）。

关键点：

如果链表中存在环，快指针和慢指针最终会相遇（即 slow == fast）。
如果链表没有环，快指针会先到达 NULL，此时链表遍历结束。

3. 时间复杂度与空间复杂度

时间复杂度： $O (n)$ ，其中 $n$ 是链表的长度。由于快慢指针分别以不同的速度遍历链表，最多需要遍历两次。
空间复杂度： $O (1)$ ，只用了常数级别的额外空间，且没有使用额外的哈希表或数组来存储链表节点。

算法实现

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct ListNode {int val;struct ListNode *next;
};// 使用快慢指针方法判断链表是否有环
bool hasCycle(struct ListNode *head) {if (head == NULL) return false;struct ListNode *slow = head;  // 慢指针struct ListNode *fast = head;  // 快指针while (fast != NULL && fast->next != NULL) {slow = slow->next;          // 慢指针每次走一步fast = fast->next->next;    // 快指针每次走两步if (slow == fast) {         // 快慢指针相遇，说明有环return true;}}return false;  // 快指针到达 NULL，说明无环
}// 测试函数
int main() {// 构造一个链表并测试环形情况struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));head->val = 3;head->next = (struct ListNode *)malloc(sizeof(struct ListNode));head->next->val = 2;head->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));head->next->next->val = 0;head->next->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));head->next->next->next->val = -4;head->next->next->next->next = head->next;  // 形成环，指向第二个节点printf("Has cycle: %s\n", hasCycle(head) ? "true" : "false");return 0;
}

代码解释

链表节点结构：
我们定义了一个链表节点结构 struct ListNode，包含一个整型值 val 和一个指向下一个节点的指针 next。
判断链表是否有环的核心函数 hasCycle：
- 使用快慢指针法：
  - 慢指针 slow 每次走一步。
  - 快指针 fast 每次走两步。
- 如果链表有环，快指针和慢指针最终会相遇；如果没有环，快指针会先走到 NULL。
- 判断相遇条件：slow == fast，如果快慢指针相遇，则链表中存在环。
main 函数：
- 构造了一个包含环的链表：head->next->next->next->next = head->next，即尾节点指向第二个节点，形成一个环。
- 调用 hasCycle 函数来判断链表是否有环，并输出结果。