LeetCode 补充题 18. 反转双向链表
题目描述
牛客原题同时要求反转单向链表和双向链表，本文对应其中的双向链表部分。
给定普通双向链表的头节点
head，请原地反转整条链表，并返回反转后的头节点。每个节点包含指向后继的
next和指向前驱的prev。反转后，两种方向的连接都必须正确，节点对象及节点值保持不变。
示例 1：
输入：head = [1,2,3]
输出：[3,2,1]
解释：数组表示从头节点沿 next 指针访问得到的节点值序列。
示例 2：
输入：head = []
输出：[]
提示：
- 输入链表不带环，头节点的
prev和尾节点的next为空。 - 不能仅通过交换节点值实现反转。
- 新头的
prev、新尾的next也应为空。
题意分析
反转一条普通双向链表，返回反转后的头节点。每个节点同时有
next和prev，反转后从新头沿next应按原来的逆序访问全部节点，从另一端沿prev也应能够反向访问。要修改的是节点之间的连接，节点值和节点对象本身都保留。原尾成为新头，原头成为新尾；空链返回空，单节点链表反转后仍是自身。
解法：原地交换前后指针
核心思路
[!blue]
反转后，一个节点原来的后继会变成前驱，原来的前驱会变成后继，因此每个节点只需交换自己的
next与prev。对每一对原本相邻的节点，两端都完成交换后，就形成方向相反、彼此一致的双向连接。难点在于交换之后如何继续遍历。当前节点的新
next已经指向原来的前驱，如果沿它走，会退回已经处理的部分。应在修改前保存原next，交换完后继续沿保存的原后继前进，保证每个原节点只处理一次。用
newHead记录最近处理的节点。按原方向走完链表时，最后处理的就是原尾节点，也就是新头。原尾的next原本为空，交换后它的prev为空；原头的prev原本为空，交换后它的next为空，所以新的两端自然保持正确边界。遍历中可能暂时存在尚未全部调整完的相邻连接，但继续前进始终依靠预先保存的原后继。整个过程结束后，所有节点都已交换两个方向，链表才整体完成反转。
解题步骤
- 从原头开始，令新头候选为空。
- 每轮先保存当前节点原来的后继
next。- 将当前
next改为原prev，再将当前prev改为保存的原后继。- 记录当前节点为新头候选，沿保存的原后继继续。
- 遍历结束后返回最后处理的节点，空链则返回空。
代码实现
class Solution {
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 {
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
}
复杂度分析
设链表长度为 $n$。
- 时间复杂度：$O(n)$，每个节点只访问一次、交换一次前后连接。
- 辅助空间复杂度：$O(1)$，只保存几个指针，复用全部原节点。
关键点总结
[!green]
- 双向反转就是每个节点同时交换前驱与后继。
- 修改前保存原后继，用它维护遍历方向。
- 最后处理的原尾是新头，原来两端的空指针也随交换改变方向。
易错点总结
[!yellow]
- 只修改
next会让正向和反向连接不一致，双向链表不能照搬只处理一个方向的写法。- 交换后沿新的
next继续走，会退回原前驱方向，可能重复访问或无法遍历全链。- 在保存原后继之前覆盖它，会失去未处理部分的入口。
- 仍返回原头只会得到新链表的尾节点，应返回最后处理的节点。
- 空链没有最后节点，新头候选应从空开始。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 206. 反转链表 | 简单 | 单链表只反转next，本题每个节点还要交换prev与next，并更新新头。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！