C++实现反转链表的两种方法

前言反转单链表是链表题里最基础的一道给定头节点把1 - 2 - 3 - 4 - 5变成5 - 4 - 3 - 2 - 1返回新的头节点。它考察的是指针操作的基本功——如何在不丢失后续节点的情况下逐个改变next的指向。常见解法有两种迭代法和递归法。迭代法用三个指针前驱、当前、后继从头走到尾边走边改指向时间 O(n)、空间 O(1)递归法先反转后面的子链表再把当前节点接到子链表尾部时间 O(n)、空间 O(n)递归栈。两种方法的结果相同选择取决于链表长度和对栈空间的容忍度。最容易写错的地方是「改指针的顺序」如果先把cur-next指向prev再想访问原来的后继就找不到了链表从这里断成两截。另一个高频错误是递归版本忘记把原头节点的next置空导致反转后的尾节点仍然指向某个节点形成环打印时死循环。本文给出两种完整实现并用同一组测试数据对比结果。代码以 C17 为准节点用new分配、用delete释放示例中明确所有权。一、节点定义与不变量// 适用于 C17struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}};反转过程中要维护一个不变量prev指向已经反转好的那一段的头cur指向尚未处理的那一段的头。每一步把cur从后者摘下来接到prev前面。走完整条链表时prev就是新链表的头cur为空。理解这个不变量迭代法的代码就不需要背每次循环先保存cur-next否则改完指向就丢了再把cur-next指向prev然后prev和cur各前进一步。二、迭代法// 适用于 C17ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* cur head;while (cur ! nullptr) {ListNode* next cur-next; // 1. 保存后继cur-next prev; // 2. 反转指向prev cur; // 3. 前驱前移cur next; // 4. 当前前移}return prev;}以1 - 2 - 3为例轮次curnext反转后已处理段prev初始1—空null1121 - null12232 - 1 - null233null3 - 2 - 1 - null3结束null—3 - 2 - 1 - null3四步的顺序不能调换next必须在改cur-next之前保存prev cur必须在cur next之前执行否则prev会跳过当前节点。空链表时循环一次都不执行返回nullptr单节点时循环执行一次cur-next被置空返回该节点。两个边界都不需要特判。三、递归法递归的思路是「先反转head-next及其后的部分再把head接到反转后的尾部」。假设reverseListRec(head-next)已经返回了子链表的新头那么原来的head-next就是子链表的尾节点让它的next指回head再把head-next置空就完成了拼接。// 适用于 C17ListNode* reverseListRec(ListNode* head) {if (head nullptr || head-next nullptr) {return head; // 空表或单节点直接返回}ListNode* new_head reverseListRec(head-next);head-next-next head; // 后继指回自己head-next nullptr; // 断开原来的指向防止成环return new_head;}以1 - 2 - 3为例递归到 3 时返回 3回到 2 这一层head是 2head-next是 3执行3-next 2、2-next nullptr返回 3回到 1 这一层head是 1head-next是 2执行2-next 1、1-next nullptr返回 3。最终得到3 - 2 - 1。head-next nullptr这一行不能省。递归返回时原头节点 1 的next仍指向 2而 2 的next已经被改成 1如果不把 1 的next清空1 和 2 就互相指向形成环。空表和单节点的基准情形也必不可少否则会解引用空指针。递归深度等于链表长度。链表有十万个节点时递归版本很可能栈溢出迭代版本没有这个问题。这是两者最实际的区别和算法是否「优雅」无关。四、完整示例下面的程序构造一条链表分别用两种方法反转打印结果后释放内存。由于反转会改变节点的连接关系同一批节点不能连续被两种方法处理两次第二次的输入已经是反转后的链表所以每种方法各构造一条新链表。// 适用于 C17#include initializer_list#include iostreamstruct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}};ListNode* reverseList(ListNode* head) {ListNode* prev nullptr;ListNode* cur head;while (cur ! nullptr) {ListNode* next cur-next;cur-next prev;prev cur;cur next;}return prev;}ListNode* reverseListRec(ListNode* head) {if (head nullptr || head-next nullptr) return head;ListNode* new_head reverseListRec(head-next);head-next-next head;head-next nullptr;return new_head;}ListNode* makeList(std::initializer_listint values) {ListNode dummy(0);ListNode* tail dummy;for (int v : values) {tail-next new ListNode(v);tail tail-next;}return dummy.next;}void printList(const ListNode* head) {for (const ListNode* p head; p ! nullptr; p p-next) {std::cout p-val;if (p-next ! nullptr) std::cout - ;}std::cout \n;}void freeList(ListNode* head) {while (head ! nullptr) {ListNode* next head-next;delete head;head next;}}int main() {ListNode* a makeList({1, 2, 3, 4, 5});a reverseList(a);printList(a); // 5 - 4 - 3 - 2 - 1freeList(a);ListNode* b makeList({1, 2, 3, 4, 5});b reverseListRec(b);printList(b); // 5 - 4 - 3 - 2 - 1freeList(b);ListNode* empty nullptr;printList(reverseList(empty)); // 空行return 0;}按标准语义两次打印都是5 - 4 - 3 - 2 - 1最后一次输出空行。makeList用栈上的哑节点简化尾插返回dummy.next哑节点本身不进入链表函数返回时自动销毁。反转后原来的头节点变成尾节点next为nullptrfreeList从新头开始遍历能释放全部节点。如果反转时漏了把尾节点的next置空freeList会在环里无限循环这比内存泄漏更难排查。五、复杂度与选择方法时间额外空间优点缺点迭代O(n)O(1)空间恒定、无栈溢出风险指针顺序需要记牢递归O(n)O(n) 栈代码短、结构清晰长链表可能栈溢出两种方法都只遍历每个节点一次。迭代法的常数更小也不需要函数调用递归法在链表长度有上限比如几千时很好用但生产代码处理未知长度的链表通常选迭代。还有一种「头插法」新建一个空链表依次取下原链表的头节点插到新链表头部。它本质上也是迭代只是多了一个哑节点。写法和三指针法等价不作为独立方法展开。常见坑点1. 先改指向再保存后继❌cur-next prev; ListNode* next cur-next;—— 此时cur-next已经变成prev原后继丢失。✅ 先ListNode* next cur-next;再改指向。2. 忘记推进prev❌cur-next prev; cur next;——prev一直停在初始值结果只反转了第一个节点。✅ 按「保存后继 → 改指向 →prev cur→cur next」四步执行。3. 递归忘记断开原头节点❌ 只写head-next-next head;不写head-next nullptr;—— 首尾成环。✅ 两步都写且基准情形覆盖空表和单节点。4. 递归基准情形只判空❌if (head nullptr) return head;后直接访问head-next—— 单节点时进入递归随后空指针解引用。✅ 条件写成head nullptr || head-next nullptr。5. 返回了旧的head❌ 迭代结束后return head;——head现在是尾节点后面的链已经断了。✅ 返回prev递归返回new_head。6. 反转后继续用旧头指针遍历❌ListNode* old head; head reverseList(head);之后从old开始遍历 ——old现在是尾节点只能看到它自己。✅ 一律从函数返回的新头开始遍历旧头只作为尾节点使用它的next已经是空。7. 释放时从旧头开始❌ 反转后仍用原来的头指针freeList(old_head)—— 旧头已是尾节点前面的节点全部泄漏。✅ 从函数返回的新头开始释放。8. 递归深度未评估❌ 对十万节点的链表直接调用递归版本 —— 栈溢出行为未定义。✅ 长链表用迭代或把递归改成显式栈。总结要点迭代法递归法核心三指针逐个改指向先反转子链表再接回当前节点关键顺序存后继 → 改指向 → 移 prev → 移 cur递归 → 后继指回 → 当前断开返回值prev子链表返回的new_head边界空表、单节点自然成立基准情形必须覆盖两者空间O(1)O(n) 栈反转链表没有复杂的算法考的是指针操作的顺序和边界。把「保存后继」放在「改指向」之前把「断开原头」写进递归把返回值定为新的头这三件事做对两种方法都不会出错。实际工程里优先用迭代除非你确定链表长度很小。