Lesson 32: 单链表反转与环检测
练习任务
难度：中-难 【面试高频】
实现技术面试中 C 语言手写代码的两道最高频题：
- reverse(head) — 三指针法原地反转单链表，返回新 head
- has_cycle(head) — Floyd 快慢指针检测链表是否有环
make_node、build_list、list_print、list_free 已提供。
本课共有 3 组测试用例：
输入 "1 2 3 4 5\n" → 输出 "5 4 3 2 1" (反转链表)
输入 "1\n" → 输出 "1" (单节点)
输入 "1 2 3 cycle\n" → 输出 "cycle detected" (环检测)提示：反转用三指针（prev/curr/next），每轮执行“保存→反转→前进”三步，顺序不能乱。环检测用快慢指针，slow 每轮 1 步，fast 每轮 2 步，步差必须为 1。
核心知识点
- 三指针反转精髓：保存 next → 反转 curr→next → 三指针前进，三步顺序不可乱
- prev 初始值 NULL，循环结束时返回 prev 而非 curr（curr==NULL 时 prev 是最后有效节点）
- Floyd 快慢指针：slow 每轮 1 步，fast 每轮 2 步，步差必须为 1
- 循环条件 while(fast && fast->next)：保证 fast->next->next 访问前 fast->next 非 NULL
- 为何 fast=3 会跳过：步差 2 时可能“跳过” slow 而不相遇
- 环入口定位：相遇后 slow 回 head，两者同速(1步)前进，再次相遇处即环入口
- 迭代 O(1) 空间 vs 递归 O(n) 栈：迭代更优，无栈溢出风险
- 快慢指针延伸：找中点、找倒数第 k 个、判断回文链表
代码框架
c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node { int data; struct node *next; };
struct node *make_node(int val) {
struct node *p = malloc(sizeof(*p));
p->data = val; p->next = NULL; return p;
}
struct node *build_list(char *nums, struct node **tail) {
struct node *head = NULL; *tail = NULL;
char *tok = strtok(nums, " ");
while (tok) {
struct node *p = make_node(atoi(tok));
if (!head) head = *tail = p;
else { (*tail)->next = p; *tail = p; }
tok = strtok(NULL, " ");
}
return head;
}
void list_print(struct node *head) {
struct node *p = head;
while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
printf("\n");
}
void list_free(struct node *head, int has_cycle) {
if (has_cycle) return;
while (head) { struct node *next = head->next; free(head); head = next; }
}
/* 三指针反转 */
struct node *reverse(struct node *head) {
// 初始化: prev = NULL, curr = head
// while (curr) 循环:
// 1. 保存下一个节点 next = curr->next
// 2. 反转: curr->next = prev
// 3. 前进: prev = curr; curr = next
// 返回 prev (它就是新 head)
}
/* Floyd 判圈 */
int has_cycle(struct node *head) {
// 空链表无环
// slow 和 fast 都从 head 出发
// while (fast 和 fast->next 都非空):
// slow 走 1 步; fast 走 2 步
// 如果 slow == fast → 相遇了 → 有环！
// fast 追到 NULL → 无环
}
int main(void) {
char line[256]; fgets(line, sizeof(line), stdin);
int len = strlen(line);
if (len > 0 && line[len-1] == '\n') line[len-1] = '\0';
int is_cycle = (strstr(line, "cycle") != NULL);
struct node *tail, *head = build_list(line, &tail);
// 如果 is_cycle: 制造环 tail->next = head, 检测并打印
// 否则: 调用 reverse 反转链表，打印结果
list_free(head, is_cycle);
return 0;
}TIP
反转的核心是三指针的“保存→反转→前进”循环。环检测的关键是步差必须为 1——否则可能永远追不上。
深度讲解
1. 三指针法原地反转
1.1 为什么需要三个指针？
反转 [1]→[2]→[3]→NULL 意味着把每个节点的 next 指向反过来。当你在改 curr->next 时，原来的 curr->next 信息会丢失——所以需要第三个指针 next 来提前保存。
三个指针各司其职:
prev: 已经反转好的部分的头节点 (初始 NULL)
curr: 当前正在处理的节点 (初始 head)
next: 下一个要处理的节点 (防止改 curr->next 后丢失剩余链表)1.2 完整步骤图解
初始: NULL [1]→[2]→[3]→NULL
↑ ↑
prev curr
第 1 轮:
步骤 1: 保存 next = curr->next
步骤 2: curr->next = prev // NULL ← [1]
步骤 3: prev = curr; curr = next // 前进
NULL ← [1] [2]→[3]→NULL
↑ ↑
prev curr
第 2 轮:
NULL ← [1] ← [2] [3]→NULL
↑ ↑
prev curr
第 3 轮:
NULL ← [1] ← [2] ← [3]
↑ curr = NULL
prev
循环结束（curr == NULL），返回 prev → 新 head = 节点 31.3 关键参数速查
| 要素 | 值 | 说明 |
|---|---|---|
| prev 初始值 | NULL | 反转后原头节点的 next 指向 NULL |
| curr 初始值 | head | 从头节点开始处理 |
| 循环条件 | curr != NULL | 处理完所有节点 |
| 返回值 | prev | curr==NULL 时 prev 是最后有效节点 |
| 时间复杂度 | O(n) | 每个节点访问一次 |
| 空间复杂度 | O(1) | 只用三个指针 |
1.4 迭代 vs 递归
| 维度 | 迭代（三指针法） | 递归 |
|---|---|---|
| 空间复杂度 | O(1) | O(n) — 递归调用栈 |
| 栈溢出风险 | 无 | n > 10000 时危险 |
| 面试推荐 | ✅ 首选 | 可提及作为备选 |
2. 环检测：Floyd 快慢指针
2.1 核心原理
两个指针从 head 同时出发：slow 每轮走 1 步，fast 每轮走 2 步。
有环: fast 必然在环中追上 slow（操场套圈原理）
无环: fast 先到达 NULL（或 fast->next == NULL）2.2 为什么必相遇？（数学证明）
slow 和 fast 都进入环后:
fast 相对于 slow 的速度 = 1 步 / 轮 (fast 走 2 步, slow 走 1 步)
环的长度为 L，两者进入环时最多相距 L-1 步。
相对速度 1 步/轮，最多 L-1 轮后必然相遇。
关键: 步差必须为 1！
若 fast 走 3 步（步差 2），可能“跳过” slow 而不相遇。
所以 Floyd 算法的精髓是: slow 走 1, fast 走 2 → 步差 = 12.3 循环条件详解
c
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1; // 有环
}
return 0; // 无环为什么必须同时检查 fast 和 fast->next？ 因为 fast 每次走 2 步，需要 fast->next->next 访问前保证 fast->next 不为 NULL。
2.4 环入口定位（扩展知识）
相遇后:
slow 回 head, fast 留相遇点
两者同速 (每轮 1 步) 前进
再次相遇处 = 环入口
数学证明:
设 head→入口距离 a, 环长 r, 相遇点距入口 s
相遇时: slow 走了 a+s+(m*r), fast 走了 a+s+(n*r)
因为 fast=2*slow, 得 a = (n-2m-1)*r + (r-s)
所以从 head 走 a 步 = 从相遇点走 (r-s) 步 → 两者在入口相遇3. 快慢指针的其他应用
| 问题 | 方法 | 原理 |
|---|---|---|
| 找链表中点 | fast 走 2 步, slow 走 1 步 | fast 到尾时 slow 在中点 |
| 找倒数第 k 个 | fast 先走 k 步, 然后同步前进 | fast 到尾时 slow 在倒数第 k |
| 判断回文链表 | 找中点 + 反转后半 + 比较 | 两端同时遍历比较 |
参考解答
练习: reverse 和 has_cycle 完整实现
c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node { int data; struct node *next; };
struct node *make_node(int val) {
struct node *p = malloc(sizeof(*p));
p->data = val; p->next = NULL; return p;
}
struct node *build_list(char *nums, struct node **tail) {
struct node *head = NULL; *tail = NULL;
char *tok = strtok(nums, " ");
while (tok) {
struct node *p = make_node(atoi(tok));
if (!head) head = *tail = p;
else { (*tail)->next = p; *tail = p; }
tok = strtok(NULL, " ");
}
return head;
}
void list_print(struct node *head) {
struct node *p = head;
while (p) { printf("%d", p->data); p = p->next; if (p) printf(" "); }
printf("\n");
}
void list_free(struct node *head, int has_cycle) {
if (has_cycle) return;
while (head) { struct node *next = head->next; free(head); head = next; }
}
/* 三指针法原地反转 */
struct node *reverse(struct node *head) {
struct node *prev = NULL;
struct node *curr = head;
while (curr) {
struct node *next = curr->next; /* 保存 */
curr->next = prev; /* 反转 */
prev = curr; /* 前进 */
curr = next;
}
return prev; /* 注意：返回 prev 而非 curr */
}
/* Floyd 快慢指针判圈 */
int has_cycle(struct node *head) {
if (!head) return 0;
struct node *slow = head;
struct node *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return 1; /* 相遇 = 有环 */
}
return 0; /* fast 到 NULL = 无环 */
}
int main(void) {
char line[256]; fgets(line, sizeof(line), stdin);
int len = strlen(line);
if (len > 0 && line[len-1] == '\n') line[len-1] = '\0';
int is_cycle = (strstr(line, "cycle") != NULL);
struct node *tail, *head = build_list(line, &tail);
if (is_cycle) {
if (tail) tail->next = head; /* 制造环 */
if (has_cycle(head)) printf("cycle detected\n");
else printf("no cycle\n");
} else {
head = reverse(head);
list_print(head);
}
list_free(head, is_cycle);
return 0;
}课堂讨论
- 反转时为什么返回 prev 而不是 curr？如果返回 curr 会发生什么？
- 快指针走 3 步行不行？举例说明什么场景下会失败。
- 快慢指针还能用来做什么？列举至少三个其他应用。
- 如何找到环的入口节点？描述具体步骤。
- 链表反转有哪些实际应用？
讨论答案
Q1: 为什么返回 prev
循环结束时 curr == NULL，返回 curr 会得到 NULL。prev 是最后一个被反转的有效节点，它就是反转后链表的新头节点。
Q2: fast=3 为什么不行
步差为 2，在环中可能“跳过” slow。例如环长为 2 时，fast=3 每轮跳过 2 个节点，可能永远追不上 slow。Floyd 算法的步差必须为 1。
Q3: 快慢指针其他应用
- 找链表中点：fast 到尾时 slow 在中点
- 找倒数第 k 个节点：fast 先走 k 步，然后同步
- 判断回文链表：找中点 + 反转后半 + 比较
Q4: 找环入口
相遇后 slow 回 head，fast 留相遇点。两者同速(每轮 1 步)前进，再次相遇处即环入口。证明见深度讲解。
Q5: 反转的实际应用
undo/redo 操作栈、浏览器前进后退、LRU 缓存中调整访问顺序、数据库中的日志倒序查询、编辑器中的撤销栈。
课后练习
- 递归反转: 实现 reverse 的递归版本，比较与迭代版的空间复杂度。
- 找环入口: 实现 find_cycle_entry 函数，返回环的入口节点指针。
- 反转部分链表: 实现 reverse_partial(head, m, n)，反转第 m 到第 n 个节点。
- 判断回文链表: 实现 is_palindrome(head)，判断链表是否是回文结构。
参考资料
- Floyd's Cycle Detection Algorithm — Wikipedia
- 《剑指 Offer》面试题 24 — 反转链表
- 《剑指 Offer》面试题 23 — 链表中环的入口节点
- 《算法导论》§10.2 — 链表操作分析
"The computing scientist's main challenge is not to get confused by the complexities of his own making." -- E. Dijkstra