LeetCode 补充题 18. 反转双向链表

约 10 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 阿里巴巴 高频面试题
标签
链表
目录

题目描述

✅ 补充题 18. 反转双向链表

题意分析

给定一条双向链表的头节点，把它就地反转并返回新的头节点。每个节点有三个字段：值、指向前一个节点的 prev、指向后一个节点的 next。

与单向链表的反转相比，这里的验收标准严格一倍：不仅从新头沿 next 走一遍要得到倒序的值，从新尾沿 prev 反着走回来也要得到正序的值。任何一个方向的指针没修好，链表就不再是一条合法的双向链表，只是恰好在某个方向上「看起来对」。

收尾条件也要明确：新头的 prev 必须为空，新尾的 next 必须为空。这两处是链表的边界标记，漏掉会让后续任何遍历都无法正常终止。

这是一道面试手写题，没有在线判题，考察点集中在指针操作的严谨性上，因此默认要求原地修改而不是重建节点，也不允许借助额外的容器。

边界共两种：链表为空时应返回空；只有一个节点时反转后仍是它自己，且两个指针都应保持为空。理想的写法是让这两种情况被主循环自然覆盖，而不是靠开头堆特判。

解法：原地交换前后指针

核心思路

最容易想到的做法是先遍历一遍把所有节点收进数组，再倒着重新串一遍指针。它确实能得到正确结果，但要付出 $O(n)$ 的额外空间，而且重新串接时同样要小心翼翼地处理两个方向，并没有真正简化问题。瓶颈在于这种做法完全没有利用双向链表本身的对称结构。

换个角度看反转这件事。反转之后，原来排在某个节点后面的节点变成了排在它前面，原来排在前面的变成了排在后面。也就是说，对每一个节点而言，它的「后继」和「前驱」这两个身份恰好互换了。而这两个身份在数据结构里就是 next 和 prev 两个字段。于是整条链表的反转被拆解成了一件极其局部的事：把每个节点的 next 和 prev 互换一次，一个节点也不多、一个节点也不少。节点之间的连接关系是自动一致的，因为若 A 原本 next 指向 B、B 原本 prev 指向 A，互换之后就变成 A 的 prev 指向 B、B 的 next 指向 A，正好是反转后应有的关系。

由此维持的不变量是：当循环走到节点 cur 时，从原链表头到 cur 之前的所有节点都已经完成了指针互换，newHead 指向其中最后一个被处理的节点；而 cur 及其之后的节点仍保持原始形态，因此可以放心地沿原始方向继续前进。

循环每处理一个节点就把 newHead 更新为它，所以退出时 newHead 停在最后一个被处理的节点上，也就是原链表的尾节点，它正是反转后的新头。这个写法顺带把两个边界包了进去：链表为空时循环一次都不进，newHead 保持为空并被直接返回；只有一个节点时循环恰好走一轮，newHead 就是它自己。

唯一需要小心的是遍历指针。互换会破坏 cur.next，所以必须在动手之前先把原来的后继存进临时变量，否则前进的路就被自己拆掉了。

解题步骤

  • 准备遍历指针 cur 指向 head，准备 newHead 初始化为空。newHead 从空起步而不是从 head 起步，是为了让空链表这一分支不需要任何特判。
  • 进入循环，条件是 cur 非空。用 cur != null 而不是 cur.next != null，前者能处理空链表并且不会漏掉最后一个节点。
  • 循环体第一件事是把 cur.next 存入临时变量 next。这一步必须在任何写操作之前完成，因为接下来的互换会覆盖 cur.next，之后再读到的就不是原来的后继了。
  • 执行互换：先把 cur.next 赋成 cur.prev，再把 cur.prev 赋成刚才存下的 next。第二句读的是临时变量而不是 cur.next，否则读到的已经是刚写进去的新值，两个字段会双双变成原来的 prev。
  • 把 newHead 更新为 cur，再让 cur 沿临时变量走到原来的后继。newHead 每轮都覆盖式更新，循环自然结束时它停在最后处理过的节点上，也就是原尾节点。
  • 循环结束后，若 newHead 非空则把它的 prev 置空。在尾节点 next 本就为空的标准双向链表上，互换之后新头的 prev 已经自动是空，这一句是冗余的；保留它是一层防御，用来兜住上游传进来的链表尾部指针不干净的情况。
  • 返回 newHead。原来的 head 此时已成为新的尾节点，返回它是最常见的错误。

以 1 <-> 2 <-> 3 走一遍：初始时节点 $1$ 的 prev 为空、next 指向 $2$；节点 $2$ 的 prev 指向 $1$、next 指向 $3$；节点 $3$ 的 prev 指向 $2$、next 为空。cur 指向节点 $1$，newHead 为空。

第一轮：next 存下节点 $2$。把节点 $1$ 的 next 改为它原来的 prev（空），再把节点 $1$ 的 prev 改为节点 $2$。此时节点 $1$ 的 prev 指向 $2$、next 为空。newHead 更新为节点 $1$，cur 走到节点 $2$。

第二轮：next 存下节点 $3$。把节点 $2$ 的 next 改为它原来的 prev（节点 $1$），再把节点 $2$ 的 prev 改为节点 $3$。此时节点 $2$ 的 prev 指向 $3$、next 指向 $1$。newHead 更新为节点 $2$，cur 走到节点 $3$。

第三轮：next 存下空。把节点 $3$ 的 next 改为它原来的 prev（节点 $2$），再把节点 $3$ 的 prev 改为空。此时节点 $3$ 的 prev 为空、next 指向 $2$。newHead 更新为节点 $3$，cur 变为空，循环结束。

收尾把 newHead（节点 $3$）的 prev 置空，它本来就是空，无变化。返回节点 $3$。校验：沿 next 走是 $3 \to 2 \to 1$，到节点 $1$ 时 next 为空正常终止；从节点 $1$ 沿 prev 反着走是 $1 \to 2 \to 3$，到节点 $3$ 时 prev 为空正常终止。两个方向都成立，反转正确。

代码实现

class Solution {
    // 遍历时必须先保存原来的 next，否则交换指针后会丢失继续向前走的入口。
    static class Node {
        int val;
        Node prev;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    public Node reverse(Node head) {
        Node cur = head;
        Node newHead = null;

        while (cur != null) {
            Node next = cur.next;

            cur.next = cur.prev;
            cur.prev = next;

            newHead = cur;
            cur = next;
        }

        if (newHead != null) {
            newHead.prev = null;
        }

        return newHead;
    }
}

type Node struct {
    // 遍历时必须先保存原来的 next，否则交换指针后会丢失继续向前走的入口。
    Val  int
    Prev *Node
    Next *Node
}

func reverse(head *Node) *Node {
    cur := head
    var newHead *Node

    for cur != nil {
        next := cur.Next

        cur.Next = cur.Prev
        cur.Prev = next

        newHead = cur
        cur = next
    }

    if newHead != nil {
        newHead.Prev = nil
    }

    return newHead
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 是链表节点数。循环体内只有三次指针赋值和一次变量更新，全是常数操作，而每个节点恰好被访问一次，指针从头走到尾不回头。
  • 空间复杂度：$O(1)$，只用了 cur、newHead、next 三个指针变量，与链表长度无关。全程原地改写节点字段，既没有开数组也没有用递归栈。

关键点总结

  • 双向链表的反转可以被彻底局部化：整体的次序颠倒，等价于每个节点独立地把 prev 与 next 两个字段互换。看穿这一点之后，代码就不再需要单向链表那种前后三指针的滑动模板。
  • 交换两个字段必须借助临时变量，且临时变量要在任何写操作之前取值。这既保证了交换本身的正确性，也保住了继续遍历的入口，一石二鸟。
  • 让边界被主循环自然覆盖，胜过在函数开头堆特判。newHead 从空起步、循环条件用 cur != null，空链表和单节点链表就都不需要额外一行代码。
  • 反转后原头变新尾、原尾变新头，返回值必须是循环里累积出来的 newHead。凡是反转类题目，「返回谁」都是和「怎么改指针」同等重要的一半。
  • 面试视角：面试官在这题上最想看的是你会不会主动说出双向的验收标准——正向遍历和反向遍历都要对。写完代码主动补一句「我从新尾沿 prev 再走一遍验证」，比写得快更能体现工程素养。
  • 面试视角：常见追问是「和反转单向链表有什么区别」。要能答出单向链表只需重定向 next、必须额外维护 prev 变量；而双向链表的 prev 字段本身就存着答案，所以反而更简单，不需要三指针。

易错点总结

  • 错误写法：互换之前不保存 cur.next → 执行 cur.next = cur.prev 后再用 cur.next 前进，读到的已是原来的 prev。在 1 <-> 2 <-> 3 上处理完节点 $1$ 时 cur 变成空，循环立刻结束，只有一个节点被反转，返回的链表只剩节点 $1$。
  • 错误写法：交换两个字段不用临时变量，写成 cur.next = cur.prev; cur.prev = cur.next; → 第二句读到的是刚写进去的新值，prev 和 next 双双变成原来的 prev。在 1 <-> 2 <-> 3 上节点 $2$ 的两个指针都会指向节点 $1$，链表出现自我缠绕。
  • 错误写法：只重定向 next 而不动 prev，照搬单向链表的三指针模板 → 沿 next 走确实能得到 $3 \to 2 \to 1$，但每个节点的 prev 仍指向原来的前驱，从节点 $1$ 沿 prev 走会走向节点 $2$ 的旧位置，双向性被破坏，且这种错误在只做正向校验时完全看不出来。
  • 错误写法：返回 head 而不是 newHead → 原头节点反转后是新尾，它的 next 已经是空，调用方沿 next 遍历只能取到一个值，看起来像是链表被清空了。
  • 错误写法：循环条件写成 cur.next != null → 一方面 head 为空时第一次判断就抛空指针异常，另一方面循环会在最后一个节点之前停下，尾节点的两个指针没被互换，新头的 prev 依然指向倒数第二个节点。
  • 错误写法：在函数开头写 if (head.next == null) return head; 之类的特判 → head 为空时先崩在这一行；即便加上判空，这类特判也只是把主循环本来就能处理的情况重复实现一遍，徒增出错面。
  • 错误写法：用递归实现，每层处理一个节点 → 逻辑虽对但栈深度等于节点数，链表长到十万级就会栈溢出，而本题的迭代写法只要三个变量。面试中被问到空间复杂度时，递归解法会直接落到 $O(n)$。
  • 错误写法：不改指针而是把节点的值倒序覆盖 → 值序列看起来是反的，但节点对象的位置没变。一旦外部还持有某个节点的引用，或者节点上挂着指针之外的其它数据，语义就完全错了；面试官说「反转链表」时默认要的是指针操作。
  • 错误写法：以为反转后还要手动把新尾的 next 置空 → 原头节点的 prev 本来就是空，互换之后它的 next 自动为空，多写一次赋值无害但说明没理清互换的效果，被追问时容易露怯。

相似题目

题目 难度 考察点
206. 反转链表 简单 单向链表只有 next 可改，必须额外维护前驱变量，是三指针模板的原型
92. 反转链表 II 中等 只反转指定区间，重点在于用哨兵头处理左边界并把反转段重新接回
25. K 个一组翻转链表 困难 分组反转且不足 k 个不翻，需要先探测剩余长度再决定是否动手
24. 两两交换链表中的节点 中等 固定长度为 $2$ 的分组反转，考察相邻三指针的赋值顺序
430. 扁平化多级双向链表 中等 同为双向链表的指针改写，但要把子链表就地插入并同步修好两个方向
143. 重排链表 中等 反转只是三步中的一步，还要配合快慢指针找中点与两链交替归并
234. 回文链表 简单 把反转当作 $O(1)$ 空间校验对称性的手段，结束后往往还需还原链表
LCR 024. 反转链表 简单 与 206 同题，适合用来对照迭代写法和递归写法的空间差异
LCR 026. 重排链表 中等 与 143 同题，可用来练习把找中点、反转、合并三段拆成独立函数
LCR 027. 回文链表 简单 与 234 同题，常被追问如何在返回前把链表复原成原状
剑指 Offer 24. 反转链表 简单 与 206 同题，面试中常作为热身，要求一次写对不调试
面试题 02.06. 回文链表 简单 与 234 同题，可对比额外用数组的 $O(n)$ 空间写法与原地反转写法