LeetCode 补充题 202. 双向链表的节点插入
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 707. 设计链表
:::
给定非循环双向链表头节点
head、下标index和值val，在该下标处插入新节点并返回新的头节点。下标从
0开始；负下标视为0，超过长度时不插入。
示例 1：
输入：
head = [1,3], index = 1, val = 2
输出：1 <-> 2 <-> 3
提示：
- 允许空表。
- 原链表的
prev、next连接正确。 -
index等于长度表示尾插。
题意分析
插入位置是两个相邻节点之间的空隙，下标等于长度时也合法。先定位这个空隙，再同时修复前向和后向链接；头插、尾插只是其中一个邻居为空的情况。
解法：定位前驱后双向连接
核心思路
[!blue]
先定位插入点的两个邻居：
prev是前驱，next是原下标 index 处的节点。目标是把prev ↔ next改成prev ↔ node ↔ next。连接按四个关系检查：
node.prev=prev、node.next=next；有前驱时令prev.next=node，有后继时令next.prev=node。前驱为空说明头插，要更新 head；后继为空说明尾插。定位循环只推进已有节点。到表尾时计数仍小于 index，说明下标超过长度，返回原表头；恰好等于长度则允许追加。负下标不进入定位循环，自然按头插处理。
解题步骤
- 从表头开始，维护前驱 prev 和后继 next，前进至 index 对应的空隙。
- 已到表尾但计数仍小于 index 时返回原表头；负下标无需前进，按头插处理。
- 创建节点，分别连接 prev 和 next，并让非空邻居反向连接新节点。
- 若 prev 为空则更新 head，返回最终表头。
代码实现
class DNode {
int val;
DNode prev;
DNode next;
DNode(int val) {
this.val = val;
}
}
class Solution {
public DNode insertAtIndex(DNode head, int index, int val) {
DNode prev = null;
DNode next = head;
int i = 0;
while (i < index && next != null) {
prev = next;
next = next.next;
i++;
}
if (i < index) {
return head;
}
DNode node = new DNode(val);
node.prev = prev;
node.next = next;
if (prev == null) {
head = node;
} else {
prev.next = node;
}
if (next != null) {
next.prev = node;
}
return head;
}
}
type DNode struct {
Val int
Prev, Next *DNode
}
func insertAtIndex(head *DNode, index int, val int) *DNode {
var prev *DNode
next, i := head, 0
for i < index && next != nil {
prev, next = next, next.Next
i++
}
if i < index {
return head
}
node := &DNode{Val: val, Prev: prev, Next: next}
if prev == nil {
head = node
} else {
prev.Next = node
}
if next != nil {
next.Prev = node
}
return head
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$，包括一个新节点。
关键点总结
[!green]
先找到插入位置的前驱和后继，再设置新节点的两条指针及两侧节点的对应指针；头插时更新头节点。
易错点总结
[!yellow]
- index 等于长度允许尾插，只有超过长度才不插入。
- 更新 next 链接后仍要更新 prev 链接，否则只能单向遍历。
- 空表插入和普通头插都需要更新返回的 head。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 707. 设计链表 | 中等 | 可复用双向链表的按下标插入与前后指针维护；该题还包含查询、删除等接口，本题仅实现节点插入。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！