LeetCode 21. 合并两个有序链表
题目描述
题意分析
给定两条按非递减顺序排列的链表，把它们的节点合并成一条仍然从小到大排列的链表，返回合并后的头节点。
合并需要保留所有节点，值相同的节点也不能丢弃。通过调整原节点的
next连接完成合并，不必复制每个节点。任意一条链表都可能为空；两条都为空时返回空链表。
解法：哨兵节点迭代合并
核心思路
[!blue]
每条链表都已排序，因此当前头节点就是这条链表剩余部分的最小值。比较两条链表的当前头节点，较小者一定是全部剩余节点中最小的，可以直接接到结果尾部；随后只推进它所属链表的指针，继续比较。值相等时先接任意一个都可以，另一个仍保留在原链表中等待处理。
用哨兵节点
dummy放在结果头部之前，tail指向结果的尾节点。这样接入第一个节点和后续节点都只需要设置tail.next，不用单独判断结果是否为空。接入后让tail向后移动，而dummy始终不动，通过dummy.next保留结果入口。当一条链表用完时，另一条的剩余节点本身有序，且都不小于已经接入的尾节点，可以直接整段接到
tail.next，无需逐个比较。最后返回dummy.next，哨兵本身不属于答案。
解题步骤
- 创建哨兵节点
dummy，令tail = dummy。- 两条链表都非空时，比较当前节点的值，将较小节点接到
tail.next。- 将被选中链表的指针移到下一个节点，再让
tail = tail.next，继续比较。- 循环结束后，将未耗尽的链表接到
tail.next，返回dummy.next。
代码实现
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
// 复用较小的当前头节点，只推进它所属的链表；哨兵值不参与比较。
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
// 接入一个节点后，只向前推进结果尾部。
tail = tail.next;
}
// 剩余后缀本身有序，可以一次接入。
tail.next = list1 != null ? list1 : list2;
return dummy.next;
}
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for list1 != nil && list2 != nil {
// 复用较小的当前头节点，只推进它所属的链表；哨兵值不参与比较。
if list1.Val <= list2.Val {
tail.Next = list1
list1 = list1.Next
} else {
tail.Next = list2
list2 = list2.Next
}
// 接入一个节点后，只向前推进结果尾部。
tail = tail.Next
}
// 剩余后缀本身有序，可以一次接入。
if list1 != nil {
tail.Next = list1
} else {
tail.Next = list2
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(m + n)$，
m、n为两条链表的长度，每个节点至多参与一次接入操作。- 空间复杂度：$O(1)$，复用原节点，只新增一个哨兵节点和少量指针。
关键点总结
[!green]
- 哨兵节点避免单独处理结果头节点。
- 循环条件必须是两条链表都非空。
- 一条链表耗尽后，可直接挂接另一条的剩余部分。
易错点总结
[!yellow]
- 返回
dummy或tail，正确结果头是dummy.next。- 接入节点后忘记移动对应链表指针或
tail。- 循环条件写成“或”，导致访问空指针。
- 忘记接上未耗尽链表的剩余部分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 23. 合并 K 个升序链表 | 困难 | 两链表归并是合并k条链表的基础子过程，可按分治成对合并。 |
| 88. 合并两个有序数组 | 简单 | 同样从两个有序来源取下一项，数组版本需避免覆盖尚未读取的数据，常从末尾合并。 |
| 148. 排序链表 | 中等 | 按有序头节点逐步拼接链表；本题合并两条链表，该题以归并排序反复合并子链表。 |
| 补充题 190. 合并两个有序链表并去重 | 中等 | 沿用两条链表比较表头、接入较小节点的方法；补充题还需跳过重复值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！