反转链表深入解析：三种解法与多语言实现

反转链表这道题,我前后见过不下十次。不管是校招机试、社招在线笔试,还是现场面试的白板环节,它就像链表题目的默认选项,稳稳坐在替补席第一位。题目描述通常就一句话——给你单链表的头节点 head,请你反转链表,并返回反转后的链表——看起来没什么含量,但真到机试现场,要在有限时间内把思路、代码、边界处理全部做对,还是能筛掉不少人。

这篇文章我把反转链表从原理到代码彻底拆一遍,覆盖迭代、递归、头插三种主流解法,分析每种写法背后的指针流转逻辑,并附上C++、C、Python三套可直接复用的实现。文章内容面向两类人:一类是准备机试和面试、想把这题吃透的求职者;另一类是平时写业务代码、想补一补数据结构基本功的开发者。读完你不仅能写出 AC 的代码,还能理解为什么每次写完都要检查那三四个容易翻车的边界条件。

1. 内容整体设计与思路拆解

1.1 为什么反转链表是机试常客

反转链表在机试里出现频率高,不是没有原因的。它考察的是链表操作最核心的能力:指针操作的正确性。数组反转你只需要交换下标,链表反转却要处理节点之间的引用关系,稍不留神就把链表改造成一个环,或者丢了一截节点。这种能力没办法靠背书获得,只能靠真正理解和反复动手。

它同时也是很多复杂题目的基础构件。判断回文链表需要先找到中点再反转后半段;每 k 个节点一组反转,是反转链表的区间版本;甚至一些 LRU 缓存的手写实现里,也要涉及双向链表的节点摘除和头部插入。你在机试中把反转链表练熟悉了,后面遇到这些变体时会轻松很多,因为操作思路都是同一套。

另外从出题人视角看,这道题区分度很好。同一个反转,有人只能背下迭代代码,边界一变就懵;有人能现场推导出递归和头插两种写法,并能清楚讲出三者的时间复杂度空间复杂度关系。机试评分时,代码正确性只是基础分,思路清晰、能应对追问,才是拿高分的关键。

1.2 三种解法,本质是一条思路

反转链表最常见的解法有三种:迭代法(三指针)、递归法、头插法。很多初学者把它们当成三个互不相干的方法去背,其实它们底层是同一个操作的不同表达。

迭代法和头插法本质上完全一样,核心都是“把当前节点从原链表摘下,放到新链表的头部”。只不过迭代法用 pre 指针充当新链表的头,头插法用一个独立的 newHead 指针充当新链表的头。递归法则是从链表尾部开始逆序处理,把“反转后半段”变成子问题,然后让当前节点的下一个节点指回自己。理解了这条主线,你会发现这三种写法的判断条件其实可以互相推导。

机试时建议优先用迭代法,理由很简单:它最直观、最容易边写边验证,也不需要担心递归深度。递归法和头插法作为备选和拓展,在面试追问时能体现理解深度,但做第一版 AC 代码时,稳定压倒一切。

2. 核心细节解析与实操要点

2.1 迭代法的指针流转,一图理清

迭代法的标准写法是三指针,代码很简短:

ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 保存后继 cur->next = pre; // 反转当前节点 pre = cur; // pre 前移 cur = next; // cur 前移 } return pre; }

很多人第一次看这段代码,觉得每行都认识,合在一起却理不清。我建议用一个三节点链表 [1 -> 2 -> 3 -> nullptr] 手动模拟一轮,你会看到指针是这样流动的:

• 初始状态:pre 指向 nullptr,cur 指向节点 1。
• 第一步,用 next 记录 cur->next,也就是节点 2。这一步非常关键,因为下一步就要修改 cur->next,如果不先保存,节点 2 就找不到了。
• 第二步,让 cur->next 指向 pre。此时节点 1 的 next 从节点 2 变成了 nullptr,相当于摘了下来。
• 第三步,pre 移动到 cur,也就是 pre 指向节点 1。
• 第四步,cur 移动到 next,也就是 cur 指向节点 2。

循环往复,直到 cur 为空时,pre 正好指向原链表的尾节点,也就是反转后新链表的头节点,直接返回 pre。

整个过程里,最容易忽略的是第一步“先保存 next”。我见过不少人在白板编程时漏掉这一行,结果是 cur->next 被改成 pre 之后,cur 再往后走时已经指向旧的前驱,链表在你手里断了。记住一个口诀:改指向之前,先备份后路。

2.2 递归法的停止条件与回溯操作

递归法的代码比迭代法更短,但理解门槛反而更高:

ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; }

递归解法要抓住两个关键点。

第一个是终止条件:head == nullptr || head->next == nullptr。空链表直接返回空,这个好理解;单节点链表它的 next 已经是 nullptr,反转后还是它自己,所以也直接返回。这两个边界放在递归里尤其重要,因为每一层递归都会检查,所有子链表走到只剩一个节点时就开始回溯。

第二个是回溯时的反转操作:head->next->next = head,这句让人困惑,我用句子翻译一下:当前节点的下一个节点,它的 next 应该指向当前节点。比如链表中节点 1 后面的节点是 2,那么在回溯阶段,就是把 2 的 next 改回 1,实现“后面的指向前面的”。紧接着head->next = nullptr是断开当前节点原来的 next,避免链表成环。

我当初学递归时有一个误区,以为递归是一层一层“正着”反转的,后来才明白:递归调用会一直走到链表尾部,真正修改指针的动作发生在回溯阶段,是一层一层“倒着”完成的。理解这个顺序之后,递归代码就再也不会背混了。

需要提醒的是,递归法在机试中有一个隐患:链表长度过长时可能栈溢出。C++ 默认栈空间对成千上万层的递归通常没问题,但如果链表长度达到几万甚至十万级别,递归就危险了。机试环境很少给这么长的链表,但你要有意识,在需要追求极致稳定性的场景,迭代法是更安全的选择。

2.3 头插法的思维模型

头插法的思路不改变链表的“方向感”,而是不断把节点摘下来,插到新链表的最前面:

ListNode* reverseList(ListNode* head) { ListNode* newHead = nullptr; while (head != nullptr) { ListNode* temp = head; head = head->next; temp->next = newHead; newHead = temp; } return newHead; }

这里我用一个日常类比:想象你有一摞盘子,每次从最上面拿一个,放到另一摞的上面。新摞的顶部永远是最后放上去的那个盘子,这就是反转的效果。

头插法和迭代法的指针操作数量完全一样,都是每轮做一次保存、一次摘除、一次挂接、一次移动。区别只在于迭代法复用了入参 head 作为遍历指针,头插法单独维护了一个 newHead。如果你在机试现场脑子和手都对迭代法熟得发腻,头插法可以作为一个快速的复核手段,互相验证结果。

三种方法的时间复杂度都是 O(n),需要遍历每个节点一次;迭代法和头插法的空间复杂度是 O(1),递归法因为调用栈的关系是 O(n)。如果面试官追问“有没有空间 O(1) 的解法”,递归写法就属于空间不达标,这时你应该立刻切到迭代法。

3. 实操过程与核心环节实现

3.1 C++ 实现:机试标准模板

机试环境多数支持 C++,我建议所有准备机试的同学把下面这套模板吃透,它包含链表节点定义、反转函数、辅助打印函数和测试主函数,你自己练习时直接复制运行就能看结果。

#include <iostream> struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} }; ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { std::cout << cur->val; if (cur->next != nullptr) std::cout << " -> "; cur = cur->next; } std::cout << std::endl; } ListNode* createList(int arr[], int n) { if (n == 0) return nullptr; ListNode* head = new ListNode(arr[0]); ListNode* cur = head; for (int i = 1; i < n; i++) { cur->next = new ListNode(arr[i]); cur = cur->next; } return head; } int main() { int arr[] = {1, 2, 3, 4, 5}; ListNode* head = createList(arr, 5); std::cout << "反转前: "; printList(head); ListNode* newHead = reverseList(head); std::cout << "反转后: "; printList(newHead); return 0; }

这套代码在 LeetCode 和主流 OJ 上都能直接跑通。有一点要注意:我写了三个构造函数,这是为了适配不同初始化场景。如果你用的 OJ 平台只提供了节点结构,不需要自己定义,那就直接写 reverseList 函数体即可,不要因为重复定义结构体导致编译冲突。

3.2 C 语言版本:从零定义链表开始

有些机试平台只支持 C 语言,这种情况下你需要自己完成结构体定义、动态内存分配和释放。C 版本的核心区别在于用struct ListNode声明结构体,并通过malloc创建节点。

#include <stdio.h> #include <stdlib.h> typedef struct ListNode { int val; struct ListNode* next; } ListNode; ListNode* createNode(int val) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->val = val; node->next = NULL; return node; } ListNode* reverseList(ListNode* head) { ListNode* pre = NULL; ListNode* cur = head; while (cur != NULL) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } void printList(ListNode* head) { ListNode* cur = head; while (cur != NULL) { printf("%d", cur->val); if (cur->next != NULL) printf(" -> "); cur = cur->next; } printf("\n"); }

C 语言版本有一个实操细节容易被忽略:反转之后原链表的头节点变成了尾节点,它的 next 已经被置为 NULL,但如果你的链表是带头节点的哑节点(dummy node)写法,反转时要格外小心,哑节点不能作为普通节点参与反转。我在机试现场处理过这类代码,最稳妥的做法是:如果题目给的 head 是第一个数据节点,就按标准三指针处理;如果 head 是哑节点,则先取head->next作为真实起始节点,反转完成后再让哑节点指向新的头。

3.3 Python 版本:引用语义的陷阱

Python 的链表操作和 C/C++ 有一点本质区别:Python 对象的赋值是引用,节点本身没有指针语法。但也正因为这个特性,反转逻辑变成纯属性操作,代码反而更清爽。

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head: ListNode) -> ListNode: pre = None cur = head while cur: next_node = cur.next cur.next = pre pre = cur cur = next_node return pre def create_list(arr): dummy = ListNode() cur = dummy for val in arr: cur.next = ListNode(val) cur = cur.next return dummy.next def print_list(head): values = [] while head: values.append(str(head.val)) head = head.next print(" -> ".join(values)) head = create_list([1, 2, 3, 4, 5]) print("反转前:", end=" ") print_list(head) new_head = reverse_list(head) print("反转后:", end=" ") print_list(new_head)

Python 版本要注意一个“隐式引用”的坑:你在循环里写cur.next = pre,Python 会直接修改这个对象属性,而不是创建副本。所以反转完成后,原来链表的尾节点变成了新链表的头,而原头节点变成了尾节点。这在逻辑上没问题,但如果你在反转后还想用旧的 head 变量去遍历,你会发现它已经指向新链表的尾节点。机试中如果你打印反转后的链表,却又用旧的 head 变量去访问,很容易得到 None 或空结果。

3.4 三种语言实现对比与选型建议

从我自己的经历来看,如果你是 C++ 选手,反转链表几乎不需要思考就能写对;如果平时用 Python 刷题,建议还是把 C++ 版本练熟,因为很多机试平台默认支持 C++ 且性能更可控。语言只是工具,核心是理解指针流转的那套逻辑,理解了,任何语言都是同一套思路。

4. 常见问题与排查技巧实录

4.1 指针丢失,链表断成两截

这是反转链表最常见的错误。典型场景是漏写ListNode* next = cur->next;这一行,或者写得太晚,导致 cur->next 被修改后,原后继节点丢失。后果是循环跑到一半,cur 变成 nullptr 或者停留在某个节点上,程序直接崩溃或输出错误链表。

排查方法很简单:在纸上画三个节点的链表,用 pre、cur、next 三个变量模拟一轮,重点检查 cur 在每轮结束后能否顺利移动到下一个节点。如果 cur 总是回到上一个节点,说明 next 保存的逻辑有问题。

4.2 边界条件:空链表和单节点链表

机试最容易出现“代码在正常样例上跑通,一提交就错”的情况。绝大多数原因都是边界条件没处理。空链表时,head 为 nullptr,迭代法直接跳过 while 循环返回 pre(nullptr),没有问题;递归法的head == nullptr终止条件也是对的。单节点链表,迭代法循环只走一次,pre 最终指向唯一节点,结果正确;递归法直接命中head->next == nullptr返回自身,也正确。

看起来两种方法都天然处理了边界,但有一个隐蔽问题:如果你的代码里把边界条件写成了head->next == nullptr却没有先判断head == nullptr,那么空链表传入时就会发生空指针解引用,直接运行时错误。所以千万别省掉head == nullptr这个判断,尤其是递归法。

4.3 递归深度过大导致栈溢出

递归法看起来很优雅,但每次递归调用都会占用栈帧。链表长度为 1000 时,递归深度就是 1000;链表长度为 100000 时,递归深度就是 100000,此时栈空间大概率不够用,程序崩溃。我在本地测试过一个长度为 10 万的链表,用递归法反转直接段错误,换成迭代法秒过。

如果你的机试环境对时间空间要求苛刻,或者题目没有明确说明链表长度,优先迭代法。如果面试官专门问递归写法,你可以先写出递归版本,然后主动补充一句“这个写法空间复杂度是 O(n),如果链表较长,我会用迭代法优化到 O(1) 空间”,这样既展示了递归理解,又展现了工程思维。

4.4 机试中的快速自测清单

写完代码后,不要急着提交。我在机试中养成了一个习惯:提交前用一组固定用例快速自测,几乎能拦截掉 90% 的低级错误。

自测时要注意:如果你在函数里修改了链表结构,打印结果必须用返回的新头节点,而不是原来的 head。这一点尤其容易踩坑,因为原地反转之后,原 head 已经不是新链表的头了,很多人下意识用原 head 打印,结果输出只有 1 一个节点,就以为自己写错了,其实只是打印错了入口。

4.5 从读题到 AC 的提速路径

机试时间紧,我建议在反转链表这道题上养成固定的答题节奏。拿到题目后先用一两句话在心里复述需求:输入是单链表头节点,输出是反转后的新头节点。然后立刻决定用迭代法,边写边在注释里标注 pre、cur、next 的职责。写完函数体后,花十秒钟走一遍边界:空链表返回什么,单节点返回什么。最后用自测用例跑一遍,确认无误再提交。

这个方法看起来简单,但能帮你建立肌肉记忆。真正到机试现场,你会感谢这种“无脑”的标准流程,它把认知负担降到最低,让你把精力留给那些更复杂的题目。

就我个人而言,反转链表这道题教会我的不是那几行代码,而是面对指针操作时的谨慎:先保存再修改、先判断为空再访问、先想边界再写循环。这些习惯在后面处理双向链表、循环链表、以及各种树的指针操作时,都是通用的。如果你也正为机试焦虑,不用贪多,先把反转链表的三种写法练到闭眼能写对,再往下一题走,这个基础打得值。