在线 -
搜索 AIGC编程网
← 返回题目列表

链表拼接 splice 是什么？为什么能在已知边界时 O(1) 接入一段节点？

中等 第 20 / 28 题 更新于 2026/07/30
链表splice拼接指针重连

简化版

链表 splice 指把一段连续节点从一个位置剪下，再接到另一个位置。只要已知这段的前驱、头、尾和插入位置，核心操作只是改几条指针，因此可以做到 O(1)；真正耗时通常在“找到边界节点”。

详细版

链表拼接常见于链表重排、LRU 移动节点、任务队列迁移、内核链表操作等场景。它的关键不是复制节点，而是复用原节点并改变连接关系。

基本思路：

  • 先确定被移动片段 [first, last]。
  • 从原位置摘下：让 beforeFirst.next = afterLast。
  • 插入到目标位置后：让 last.next = target.next，target.next = first。
  • 如果是双向链表，还要同步维护 prev。

splice 的效率来自“移动一段节点不需要逐个搬运”。但如果不知道 last 或 beforeFirst，仍要遍历查找，整体复杂度可能变成 O(n)。

完整版教学

一、splice 解决的不是复制，而是重接

很多链表操作本质上都是 splice。比如把链表后一半插到前一半中间、把某个缓存节点移动到头部、把一个任务队列整体挂到另一个队列末尾，本质都是剪下一段，再接到新位置。

单链表片段可以表示为：

before -> first -> ... -> last -> after

如果要把 [first..last] 移走，第一步就是让 before.next = after。这一步完成后，这段节点从原链表中脱离，但片段内部顺序仍然保留。然后再把它接到目标位置即可。

二、为什么已知边界时可以 O(1)

链表和数组最大的不同是：数组移动一段元素通常需要搬运内存，链表移动一段节点只改边界连接。片段中间有 1000 个节点，也不需要逐个改它们的 next。

插入到 target 后面的过程：

target -> oldNext
first -> ... -> last

改成：
target -> first -> ... -> last -> oldNext

代码形态：

const oldNext = target.next;
target.next = first;
last.next = oldNext;

这里没有循环，所以在已知 target、first、last 的前提下是 O(1)。真正的复杂度经常藏在“怎么找到这些节点”里。

三、单链表 splice 为什么需要前驱

如果要摘下一段 [first..last]，只知道 first 不够。你还要知道 beforeFirst，因为原链表需要绕过这段。

A -> B -> C -> D -> E
     ^         ^
   first      last

要移走 B-C-D，必须让 A.next = E

单链表节点不知道前驱，所以 beforeFirst 通常要提前保存。很多链表题之所以用 dummy 或 prev，就是为了在 splice 时能安全修改入口。

四、双向链表 splice 要维护两个方向

双向链表 splice 更强大，也更容易写错。摘下片段时，要让前后两端互相连接；插入时，也要让目标位置两侧和片段两端互相连接。

操作单链表需要改双向链表还要改
摘下片段before.next = afterafter.prev = before
插入片段target.next = first; last.next = oldNextfirst.prev = target; oldNext.prev = last
更新头尾可能需要可能需要

双向链表最好配合哨兵节点，否则头尾边界会产生很多空指针判断。LRU 中把节点移动到头部，其实就是“摘下单节点 + 插到头哨兵后”，这就是最小 splice。

五、splice 和重建链表的区别

重建链表是新建节点，把值复制过去；splice 是移动原节点。两者输出可能相同，但语义不同。

如果节点还被外部引用，重建会让外部引用指向旧节点，新的链表节点和旧引用没有关系。splice 则保留节点身份，只改变它所在的位置。

外部 map[key] -> nodeX

LRU 缓存必须移动原节点，否则哈希表中保存的节点引用就会失效。这个例子能帮助你在面试中解释“为什么不能简单复制值或新建节点”。

六、边界和复杂度如何回答

splice 前要确认几个边界：片段是否为空、目标位置是否在片段内部、是否会影响 head/tail、是否是同一条链表内移动。目标位置落在被移动片段内部时，直接移动可能产生环或无效操作。

复杂度要拆开说：

已知边界节点：O(1)
需要查找边界：O(n)
移动片段长度 m：不影响重连成本

记忆钩子：splice 的关键是“改边界，不搬中间”。中间有多少节点不重要，找边界才重要。

七、常见误区与追问

  • 误区：移动一段长度为 m 的链表一定是 O(m)。 如果边界已知，只改几条指针，重连本身是 O(1)。
  • 误区：只知道片段头就能摘下片段。 单链表还需要片段前驱，否则原链表无法绕过片段。
  • 误区：双向链表只改 next 即可。 prev 不同步会导致反向遍历错误。
  • 追问：splice 会新建节点吗？ 不会，它移动原节点；如果新建节点，那是复制或重建。
  • 追问：目标位置在片段内部怎么办？ 通常应判定为无效或直接返回，否则可能形成环或破坏链表。

八、加强记忆

splice 可以理解成链表里的“剪切粘贴”。剪切时让原位置前后接上，粘贴时让目标位置接入片段头尾。它的效率来自不搬中间节点，但前提是边界节点已经拿到；如果边界还要找，复杂度就要把查找成本算进去。