LeetCode 补充题 190. 合并两个有序链表并去重
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 21. 合并两个有序链表
:::
给定两条互不共享节点的非降序无环链表，合并为一条非降序链表，相同值只保留一个节点。
允许修改
next指针。
示例 1：
输入：
a = [1,2,2,4], b = [1,3,4]
输出：[1,2,3,4]
解释： 数组形式表示两条链表的节点值，合并后每个不同值只保留一个节点。
提示：
- 两条链表均非降序、无环，且不共享节点。
- 允许修改
next，结果中每个值只保留一个节点。
题意分析
两条输入链表已经有序，可以直接复用节点归并。重复值既可能来自同一条链，也可能分散在两条链中；结果只保留每个值第一次被选中的节点。
解法：有序归并时跳过重复值
核心思路
[!blue]
每次从两条链表当前表头中取较小者，某一条耗尽后继续取另一条，因此取出的值整体非降序。相同值必然连续出现，只要比较当前节点与结果尾节点的值，就能判断是否应当保留。
先推进被选中链表的输入指针，再决定是否连接该节点，避免修改链接后丢失未处理部分。结果为空或尾值不同时，让尾指针接上当前节点并前移；否则只消费输入，不改变结果尾部。
被复用节点的旧 next 可能仍连着重复后缀，循环结束必须将结果尾部的 next 置空。哨兵统一处理空结果，两个输入都为空时自然返回空链表。
解题步骤
- 从两条链头选较小节点，并先推进对应输入指针。
- 结果为空或该节点值与结果尾值不同，才把它接入。
- 全部输入消费后断开结果尾节点旧 next，返回哨兵之后的头。
代码实现
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public ListNode mergeUnique(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (a != null || b != null) {
ListNode node;
if (b == null || a != null && a.val <= b.val) {
node = a;
a = a.next;
} else {
node = b;
b = b.next;
}
if (tail == dummy || tail.val != node.val) {
tail.next = node;
tail = node;
}
}
tail.next = null;
return dummy.next;
}
}
type ListNode struct {
Val int
Next *ListNode
}
func mergeUnique(a, b *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for a != nil || b != nil {
var node *ListNode
if b == nil || a != nil && a.Val <= b.Val {
node = a
a = a.Next
} else {
node = b
b = b.Next
}
if tail == dummy || tail.Val != node.Val {
tail.Next = node
tail = node
}
}
tail.Next = nil
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n+m)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
输入有序保证重复值连续出现；只比较输出尾值便足以去重，不需要额外集合。
易错点总结
[!yellow]
- 跳过重复节点时，输入指针仍需前移，否则循环无法结束。
- 只比较结果尾值即可，但必须先判断结果是否为空。
- 最后断开旧 next，才能保证被舍弃的尾部节点不会残留在结果中。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 21. 合并两个有序链表 | 简单 | 复用两条升序链的归并，本题接入节点前还与输出尾值比较。 |
| 83. 删除排序链表中的重复元素 | 简单 | 归并后的同值节点必相邻，可以复用相邻重复值只留一个的判断。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！