LeetCode 补充题 108. 交替合并两个链表
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 143. 重排链表
:::
给你两条无环单链表的头节点
a和b，请按照a1 → b1 → a2 → b2 → …的顺序交替合并两条链表。当其中一条链表的节点用完后，将另一条链表的剩余部分接到结果末尾。请原地修改节点的
next指针，并返回合并后的头节点。
示例 1：
输入：
a = [1,2,3], b = [4,5]
输出：[1,4,2,5,3]
解释： 先取 a 的节点，再取 b 的节点，b 用完后接上 3。
示例 2：
输入：
a = [], b = [4,5]
输出：[4,5]
解释： 第一条为空，直接返回第二条。
提示：
- 两条输入不共享节点。
- 任意一条可以为空。
题意分析
结果从第一条链表开始交替取节点，不按数值大小排序，也不创建节点副本。因此关键在于改写连接时仍能找到两条链表各自未处理的部分。
每轮只需要连接当前的两个节点。一边耗尽后，另一边剩余节点原本就按所需顺序连接，可以整段保留，不必继续遍历。
解法：保存后继后交替连接
核心思路
[!blue]
a、b分别指向两条链表尚未交替连接的首节点；已经完成的前缀顺序正确。先保存nextA = a.next和nextB = b.next，再令a.next = b，避免丢失原来的后继。如果
nextA为空，第一条链表已经用完，此时保持b.next的原连接即可接上第二条的全部余项，直接结束。否则令b.next = nextA，把结果接回第一条链表，再让a、b分别前进到保存的后继。若第二条先耗尽，第一条的剩余连接已经由上一轮接好，循环自然结束。第一条初始为空时直接返回第二条；否则最初的
a始终是结果头节点。
解题步骤
- 保存 a、b 各自的原后继，再把 a 接到 b。
- 若第一条已到尾，保留 b 的原后续并结束。
- 否则将 b 接回 a 的后继，同时推进两条链。
代码实现
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public ListNode interleave(ListNode a, ListNode b) {
if (a == null) {
return b;
}
ListNode head = a;
while (a != null && b != null) {
ListNode nextA = a.next;
ListNode nextB = b.next;
a.next = b;
if (nextA == null) {
break;
}
b.next = nextA;
a = nextA;
b = nextB;
}
return head;
}
}
type ListNode struct {
Val int
Next *ListNode
}
func interleave(a, b *ListNode) *ListNode {
if a == nil {
return b
}
head := a
for a != nil && b != nil {
nextA, nextB := a.Next, b.Next
a.Next = b
if nextA == nil {
break
}
b.Next = nextA
a = nextA
b = nextB
}
return head
}
复杂度分析
- 时间复杂度：$O(\min(n,m))$，每轮各处理一个节点，剩余链无需遍历；
n、m为两条链表长度。- 空间复杂度：$O(1)$，只使用固定数量的节点指针。
关键点总结
[!green]
每次只改当前两个节点的连接；先保存后继，才能始终握住两段尚未处理的链。
易错点总结
[!yellow]
输入共享节点会导致重复连接甚至环，本题明确排除该情况；不能只交换节点值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 143. 重排链表 | 中等 | 重排链表需要先找中点并反转后半段，本题已经给出两条独立链表，只需交替合并。 |
| 21. 合并两个有序链表 | 简单 | 同样原地重连两条链表，原题按大小决定下一节点，本题固定交替并追加剩余部分。 |