力扣 Hot 100 之 206. 反转链表：面试官的“开胃菜”-平芜编程栈

206. 反转链表这道题在链表界的地位，大约等同于编程语言里的 Hello World。

虽然它是简单题，但据我观察，能一遍 bug free且能清晰讲出递归逻辑的人，其实并没有想象中那么多。很多人脑子会了，手一写，NPE（空指针）了，或者链表断了。

今天咱们就来彻底搞定它，顺便聊聊怎么在面试里把这道题写出“花”来。

题目是个啥？

给你一个单链表的头节点head，请你反转链表，并返回反转后的头节点。

输入：1 -> 2 -> 3 -> 4 -> 5 -> NULL

输出：5 -> 4 -> 3 -> 2 -> 1 -> NULL

看着简单吧？不就是把箭头调个头吗？

嘿，链表这东西最烦人的就是：由于它是单向的，你一旦回头，就找不到前任了；一旦往前走，就找不到后路了。所以，操作指针的时候得格外小心。

策略一：双指针迭代法

这是最推荐的面试写法。逻辑清晰，空间复杂度 O(1)，不容易出错。

核心心法：三人行

虽然叫双指针，但其实我们需要三个变量来玩转这场“移形换影”：

curr（当前节点）：我现在在哪。
prev（前驱节点）：我要把箭头指给谁（我的新后继）。
next（临时节点）：最重要的备胎。在我改变心意指向prev之前，我得先记下来我原本要去哪，不然一断链，后面的节点全丢了。

动图脑补流程

想象一下，你站在curr(比如节点 2) 的位置：

备份：先把curr.next(节点 3) 存到next变量里。（防丢失）
掉头：把curr.next指向prev(节点 1)。（关键一步，链子反了）
挪窝：
- prev往前走一步，变成curr。
- curr往前走一步，变成刚才备份的next

class Solution { public ListNode reverseList(ListNode head) { // prev 初始化为 null，因为反转后，原本的头节点要指向 null ListNode prev = null; ListNode curr = head; while (curr != null) { // 1. 记下原本的下一步去哪（保存现场） ListNode nextTemp = curr.next; // 2. 斩断情丝，回首掏（指针反转） curr.next = prev; // 3. 整体向后移动 prev = curr; curr = nextTemp; } // 循环结束时，curr 是 null，prev 才是新的头节点（原本的尾巴） return prev; } }

防坑指南：

千万别忘了最后返回的是prev，不是curr（循环结束时curr已经是null了）。
别忘了初始化prev = null，否则反转后的尾巴没法结束。

策略二：递归法

如果你想在面试官面前秀一下你的抽象思维能力，或者想让代码看起来短小精悍，可以用递归。

但说实话，这玩意儿非常绕，脑子不好使的时候容易把自己绕进去。

核心心法：甩锅

递归的精髓在于信任。

假设我们有一个函数 reverseList(head)，它的作用是把以 head 为头的链表反转，并返回新的头。

面对1 -> 2 -> 3 -> 4 -> 5：

我（节点 1）想反转整个链表。
我太懒了，我先对 head.next（也就是节点 2）说：“兄弟，你带着后面那帮人先去反转一下。”
ListNode newHead = reverseList(head.next);
假设第 2 步成功了，现在的局面是：
1 -> 2 <- 3 <- 4 <- 5
注意：此时 1 还连着 2，但 2 已经是后面那串反转后的链表的“尾巴”了。
关键操作：我要让 2 指回 1。
head.next.next = head; （翻译：我下家的下家，变成我自己）
断后路：1 现在是新的尾巴了，必须指向 null，否则就死循环了。
head.next = null;

class Solution { public ListNode reverseList(ListNode head) { // 递归终止条件：链表为空，或者只有一个节点，那还反转个屁，直接返回 if (head == null || head.next == null) { return head; } // 1. 甩锅：先让后面的节点去反转 // newHead 只是为了最后返回用，中间过程完全不碰它 ListNode newHead = reverseList(head.next); // 2. 关键：把当前节点挂到后面那串链表的尾巴上 // head.next 此时就是后面那串的尾节点 head.next.next = head; // 3. 断开原来的连接，防止环路 head.next = null; return newHead; } }

优缺点分析：