链表的反转：迭代反转、递归反转、局部反转
链表反转，说实话，是面试里考得最多的问题之一。我当年去大厂面试，第一轮手撕代码就是这道题。当时我用了递归，面试官点点头，又让我用迭代写一遍。嗯，两种方法都得会。
反转的核心思想是什么？说白了就是改变指针的方向。原来 a→b→c，变成 a←b←c。听起来简单，但写起来容易晕。我见过不少同事，写反转写到把自己绕进去。今天咱们把三种方式都捋一遍。
核心要点：反转链表不改变节点本身，只改变节点之间的指向关系。你操作的是指针，不是数据。
一、迭代反转
迭代反转是最直观的方式。你需要三个指针：prev、curr、next。为什么是三个？因为你要断开当前节点的 next 指针之前，得先保存它后面的节点，不然就找不回来了。
我刚开始学的时候，总想着两个指针就够了。结果一跑就段错误，链表断了。后来养成了习惯：改指向之前，先保存后路。
// 迭代反转链表
struct ListNode* reverseList_iterative(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* next = NULL;
while (curr != NULL) {
// 先保存下一个节点
next = curr->next;
// 反转当前节点的指向
curr->next = prev;
// 三个指针整体后移
prev = curr;
curr = next;
}
// 循环结束时，prev 指向新头
return prev;
}你看这个流程：保存→反转→移动。每一步都很清晰。我曾经在嵌入式项目里用这个方式反转一个设备链表，跑了几年没出过问题。
小技巧：画图！在纸上画三个方框代表节点，用箭头标出指针变化。我每次教新人，都让他们先画图再写代码。画明白了，代码自然就写对了。
二、递归反转
递归反转，代码更短，但理解起来需要一点想象力。它的思路是：先反转后面的链表，再把当前节点接到后面。
你想想看，如果我已经把 head->next 后面的部分反转好了，那现在要做什么？只需要让 head->next->next = head，再把 head->next 置空就行了。
// 递归反转链表
struct ListNode* reverseList_recursive(struct ListNode* head) {
// 递归终止条件：空链表或只有一个节点
if (head == NULL || head->next == NULL) {
return head;
}
// 反转后面的链表
struct ListNode* newHead = reverseList_recursive(head->next);
// 把当前节点接到后面
head->next->next = head;
head->next = NULL;
return newHead;
}这里有个坑：head->next->next = head 这行，很多人写成 head->next = head，那就成环了。我曾经调试一个递归反转的 bug，花了两个小时才发现是这里写反了。嗯，血的教训。
注意：递归反转会使用栈空间，深度等于链表长度。如果链表很长（比如上万节点），小心栈溢出。嵌入式环境里栈通常比较小，我一般优先用迭代法。
三、局部反转
局部反转，就是只反转链表中的一段。比如把第 m 个节点到第 n 个节点之间的部分反转，其他部分保持不变。
这个需求我在实际项目中遇到过。有一次要处理一个数据包链表，需要把中间一段顺序颠倒一下。当时我写了个局部反转，同事看了直呼巧妙。
思路是这样的：
- 先找到第 m-1 个节点（反转段的前驱）
- 从第 m 个节点开始，用迭代法反转 n-m+1 个节点
- 把反转后的段重新接回原链表
// 局部反转：反转从 m 到 n 的节点（1-based）
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if (head == NULL || m == n) {
return head;
}
// 加一个虚拟头节点，方便处理 m=1 的情况
struct ListNode dummy;
dummy.next = head;
struct ListNode* prev = &dummy;
// 1. 找到第 m-1 个节点
for (int i = 1; i < m; i++) {
prev = prev->next;
}
// 2. 开始反转
struct ListNode* curr = prev->next;
struct ListNode* next = NULL;
struct ListNode* tail = curr; // 反转段的尾巴，最后要接上
for (int i = m; i <= n; i++) {
next = curr->next;
curr->next = prev->next;
prev->next = curr;
curr = next;
}
// 3. 把反转后的尾巴接上剩余部分
tail->next = curr;
return dummy.next;
}这段代码里，我用了虚拟头节点 dummy。为什么？因为如果 m=1，反转段包含头节点，没有前驱节点，处理起来很麻烦。加个虚拟头，一切就统一了。这个技巧我在很多链表操作里都用过。
关键点：局部反转的难点在于边界处理。m=1 时头节点会变，n=链表长度时尾巴要接 NULL。画个图，把每个指针的最终位置标清楚，再动手写。
三种方式对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 迭代反转 | O(n) | O(1) | 通用，推荐日常使用 |
| 递归反转 | O(n) | O(n)（栈空间） | 链表较短，代码简洁优先 |
| 局部反转 | O(n) | O(1) | 需要反转部分节点 |
我个人习惯，能迭代就不递归。不是递归不好，而是嵌入式环境里栈资源太宝贵。你想想看，一个链表几千个节点，递归下去栈就爆了。迭代法三个指针走天下，多稳。
知识体系图
下面这张图展示了链表反转的三种方式及其关系，帮你理清思路：
我的建议：先掌握迭代反转，这是基本功。递归反转用来理解递归思想，面试时可能会考。局部反转是实际工程中常用的，处理数据包、任务队列时经常用到。
好了，链表反转就讲到这里。三种方式各有千秋，你根据实际场景选就行。记住一点：画图永远比硬想快。我到现在写链表操作，第一件事还是拿笔在纸上画。
公众号:蓝海资料掘金营，微信deep3321