在技术面试的算法题库中，LeetCode 206 “反转链表” 是一道标志性的题目。它看似简单，却精准地区分了编程者对于基础数据结构的理解层次。透彻掌握LeetCode 206 反转链表迭代与递归这两种经典解法，其核心价值远不止于通过一道题。它象征着你对指针（或引用）操作的精髓、递归思想的本质、以及空间/时间复杂度权衡的深刻领悟。这道题是理解更复杂链表问题（如分组反转、K个一组反转）的基石，也是面试官考察候选人代码简洁性、逻辑清晰度和思维灵活性的绝佳试金石。
一、问题重述与核心：理解“反转”的操作本质
题目要求很简单：给定单链表的头节点 `head`，请你反转链表，并返回反转后的头节点。关键在于，我们必须原地修改链表，而不能创建新的节点。这意味着所有操作都依赖于改变节点之间 `next` 指针的指向。
假设原始链表为：1 -> 2 -> 3 -> 4 -> 5 -> NULL
反转后应为：5 -> 4 -> 3 -> 2 -> 1 -> NULL
这个过程的本质，是将每个节点的 `next` 指针，从指向后继改为指向前驱。为了实现这一点，我们需要在遍历过程中，始终维护好当前节点、前驱节点和后继节点的关系，以防链表断裂。这正是LeetCode 206 反转链表迭代与递归两种解法共同面对的核心操作。
二、迭代解法：步步为营的指针“三重奏”
迭代法是符合直觉的“正向”思维，通过循环逐个扭转指针方向。
算法步骤（双指针法）：
1. **初始化三个指针（或概念）**： - `prev`：指向前一个节点，初始化为 `null`（因为反转后原头节点的 next 应指向 null）。 - `curr`：指向当前正在处理的节点，初始化为 `head`。 - `nextTemp`：临时保存当前节点的下一个节点，防止链表断裂。
2. **遍历循环**：当 `curr` 不为 `null` 时，执行以下“四步舞”： a. **保存后路**：`nextTemp = curr.next;` // 先记住下一个要处理的节点 b. **扭转方向**：`curr.next = prev;` // 将当前节点的 next 指向前一个节点，完成局部反转 c. **双指针前移**：`prev = curr;` // prev 移动到当前已处理好的新链表头 d. `curr = nextTemp;` // curr 移动到之前保存的下一个待处理节点
3. **返回新头**：循环结束时，`curr` 为 `null`，`prev` 正好指向原链表的最后一个节点，即新链表的头节点。返回 `prev`。
代码实现：
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // 保存下一个
curr.next = prev; // 反转指针
prev = curr; // prev 前移
curr = nextTemp; // curr 前移
}
return prev; // 此时prev是新头
}
复杂度分析： - **时间复杂度 O(n)**：遍历链表一次，n 为链表长度。 - **空间复杂度 O(1)**：只使用了几个固定指针变量，是真正的原地反转。
迭代法的优势在于逻辑直接，空间效率极致，是生产环境中更常用的做法。
三、递归解法：从后向前构建的“递归栈”艺术
递归解法体现了“反向”思维，其关键在于理解递归的递推关系和回归过程。它从链表的末尾开始反转。
算法思想：
1. **递推阶段**：递归深入，直到链表末尾（`head == null || head.next == null`），这个末尾节点就是未来新链表的头节点，我们将其一路返回。 2. **回归阶段**：在每一层递归返回时，我们让当前节点的下一个节点（`head.next`）指向自己（`head`），然后再断开自己原来的指向（`head.next = null`）。
理解这个“反转操作”发生的位置至关重要：它发生在递归函数开始返回之后，即从链表尾部开始向前逐个处理。
代码实现：
public ListNode reverseList(ListNode head) {
// 递归终止条件：空链表或只有一个节点，无需反转，直接返回
if (head == null || head.next == null) {
return head;
}
// 递归调用，reverseList(head.next) 会返回反转后子链表的头节点
ListNode newHead = reverseList(head.next);
// 关键操作：让当前节点的下一个节点指向自己，完成局部反转
head.next.next = head;
// 断开当前节点原来的指向，防止成环（在非末尾节点，这个指向后续会被上一层的操作覆盖或修正）
head.next = null;
// 返回新的头节点，这个头节点在底层递归已被确定，并一路传递上来
return newHead;
}
以链表 1->2->3->null 为例，递归栈的示意图：
递推： reverse(1) -> reverse(2) -> reverse(3) （发现3.next为null，返回3给上一层）
回归：
- 在 reverse(2) 层：`head`是2，`head.next`是3。执行`3.next = 2`，`2.next = null`。此时链表局部为 1->2<-3，且2指向null。返回`newHead`(即3)。
- 在 reverse(1) 层：`head`是1，`head.next`是2。执行`2.next = 1`，`1.next = null`。此时链表变为 1<-2<-3。返回`newHead`(即3)。
复杂度分析： - **时间复杂度 O(n)**：递归深度为链表长度 n，每个节点处理一次。 - **空间复杂度 O(n)**：递归调用栈的深度为 n，这是递归解法的主要代价。
递归解法的优势是代码极其简洁，体现了分治思想。但它对理解递归有较高要求，且空间复杂度较高。在“鳄鱼java”网站的算法讨论区中，递归解法常作为理解递归思维的经典案例被深入剖析。
四、深度对比：迭代与递归的思维模式差异
理解LeetCode 206 反转链表迭代与递归的差异，能提升你的算法设计能力。
1. 思维方向： - **迭代**：从前到后，正向拆解问题。思考“我现在有什么（prev, curr），下一步该怎么操作”。 - **递归**：从后到前，先假设子问题已解决（“如果后面的链表已经反转好了”），再处理当前节点。这是一种“自顶向下”再“自底向上”的思维。
2. 空间与性能： - **迭代**：空间 O(1)，是时间和空间的最优解，适合所有场景，尤其是链表很长时。 - **递归**：空间 O(n)，存在栈溢出风险（虽然对于面试链表长度通常安全）。但其简洁性在代码审查和表达算法思想时很有优势。
3. 适用性与扩展： - **迭代**：是基础，必须熟练掌握。其指针移动逻辑是解决其他复杂链表题（如反转部分链表）的模板。 - **递归**：理解它有助于解决更复杂的递归链表问题，如“两两交换链表节点”（LeetCode 24）。
五、常见误区与面试精讲要点
在实现和讲解时，请注意：
迭代法误区： - **忘记保存`curr.next`**：直接操作会导致链表断裂。 - **循环终止条件错误**：应是`while(curr != null)`，而不是`while(curr.next != null)`，否则会漏掉最后一个节点。 - **返回错误节点**：最后应返回`prev`，而不是`curr`（此时`curr`为`null`）。
递归法误区： - **终止条件不完整**：必须同时处理`head == null`（空链表）和`head.next == null`（递归基线）两种情况。 - **对`newHead`的理解错误**：`newHead`在整个递归过程中指向同一个节点（原链表的尾节点），它被层层传递回来，而不是每层都新建。 - **无法清晰描述操作顺序**：面试时必须能画出递归栈，说明操作是在“回归”阶段完成的。
面试讲述要点： 当被要求解答时，你可以： 1. 先简述迭代法，强调其O(1)空间的优势，并写出代码。 2. 然后说：“除此之外，这道题还有一个非常优雅的递归解法，它体现了递归思想的巧妙……”再阐述递归解法。 3. 最后对比两者，并指出在实际工程中，出于性能考虑，迭代法更常用；但递归解法对于理解递归思维很有帮助。
六、总结与进阶思考
彻底掌握LeetCode 206 反转链表迭代与递归，为你打开了链表算法的大门。迭代法教你如何精准地操控指针，步步为营；递归法则带你领略分解问题与组合结果的数学美感。
请记住，在面试中，清晰地解释清楚指针每一步的变化，远比默写代码更重要。建议你在理解的基础上，关闭本文，在白板上分别手写两种解法，并模拟讲解。
现在，你已经掌握了反转整个链表的方法。那么，可以进一步思考：如果要反转链表的一部分（LeetCode 92），或者每k个节点一组进行反转（LeetCode 25），你的迭代法和递归法思路该如何调整和组合？这将是检验你是否真正理解本题的绝佳试炼。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
