前言

反转单链表是链表题里最基础的一道：给定头节点，把1 -> 2 -> 3 -> 4 -> 5变成5 -> 4 -> 3 -> 2 -> 1，返回新的头节点。它考察的是指针操作的基本功——如何在不丢失后续节点的情况下，逐个改变next的指向。

常见解法有两种：迭代法和递归法。迭代法用三个指针（前驱、当前、后继）从头走到尾，边走边改指向，时间 O(n)、空间 O(1)；递归法先反转后面的子链表，再把当前节点接到子链表尾部，时间 O(n)、空间 O(n)（递归栈）。两种方法的结果相同，选择取决于链表长度和对栈空间的容忍度。

最容易写错的地方是「改指针的顺序」：如果先把cur->next指向prev，再想访问原来的后继就找不到了，链表从这里断成两截。另一个高频错误是递归版本忘记把原头节点的next置空，导致反转后的尾节点仍然指向某个节点，形成环，打印时死循环。

本文给出两种完整实现，并用同一组测试数据对比结果。代码以 C++17 为准，节点用new分配、用delete释放，示例中明确所有权。

一、节点定义与不变量

// 适用于 C++17
struct 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各前进一步。

二、迭代法

// 适用于 C++17
ListNode* 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为例：

四步的顺序不能调换：next必须在改cur->next之前保存；prev = cur必须在cur = next之前执行，否则prev会跳过当前节点。

空链表时循环一次都不执行，返回nullptr；单节点时循环执行一次，cur->next被置空，返回该节点。两个边界都不需要特判。

三、递归法

递归的思路是「先反转head->next及其后的部分，再把head接到反转后的尾部」。假设reverseListRec(head->next)已经返回了子链表的新头，那么原来的head->next就是子链表的尾节点，让它的next指回head，再把head->next置空，就完成了拼接。

// 适用于 C++17
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;
}

以1 -> 2 -> 3为例，递归到 3 时返回 3；回到 2 这一层，head是 2，head->next是 3，执行3->next = 2、2->next = nullptr，返回 3；回到 1 这一层，head是 1，head->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 就互相指向，形成环。空表和单节点的基准情形也必不可少，否则会解引用空指针。

递归深度等于链表长度。链表有十万个节点时，递归版本很可能栈溢出；迭代版本没有这个问题。这是两者最实际的区别，和算法是否「优雅」无关。

四、完整示例

下面的程序构造一条链表，分别用两种方法反转，打印结果后释放内存。由于反转会改变节点的连接关系，同一批节点不能连续被两种方法处理两次（第二次的输入已经是反转后的链表），所以每种方法各构造一条新链表。

// 适用于 C++17
#include <initializer_list>
#include <iostream>

struct 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_list<int> 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 -> 1
freeList(a);

ListNode* b = makeList({1, 2, 3, 4, 5});
b = reverseListRec(b);
printList(b); // 5 -> 4 -> 3 -> 2 -> 1
freeList(b);

ListNode* empty = nullptr;
printList(reverseList(empty)); // 空行
return 0;
}

按标准语义，两次打印都是5 -> 4 -> 3 -> 2 -> 1，最后一次输出空行。makeList用栈上的哑节点简化尾插，返回dummy.next；哑节点本身不进入链表，函数返回时自动销毁。

反转后，原来的头节点变成尾节点，next为nullptr；freeList从新头开始遍历，能释放全部节点。如果反转时漏了把尾节点的next置空，freeList会在环里无限循环，这比内存泄漏更难排查。

五、复杂度与选择

两种方法都只遍历每个节点一次。迭代法的常数更小，也不需要函数调用；递归法在链表长度有上限（比如几千）时很好用，但生产代码处理未知长度的链表，通常选迭代。

还有一种「头插法」：新建一个空链表，依次取下原链表的头节点插到新链表头部。它本质上也是迭代，只是多了一个哑节点。写法和三指针法等价，不作为独立方法展开。

常见坑点

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. 递归深度未评估

❌ 对十万节点的链表直接调用递归版本 —— 栈溢出，行为未定义。

✅ 长链表用迭代；或把递归改成显式栈。

总结

反转链表没有复杂的算法，考的是指针操作的顺序和边界。把「保存后继」放在「改指向」之前，把「断开原头」写进递归，把返回值定为新的头，这三件事做对，两种方法都不会出错。实际工程里优先用迭代，除非你确定链表长度很小。