LeetCode 补充题 111. 提取有序链表中的重复值
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 83. 删除排序链表中的重复元素
:::
给你一条按非降序排列的单链表的头节点
head，只保留出现至少两次的值，并且每个保留的值只留下一个节点。请原地调整节点的
next指针，保持结果按非降序排列，并返回新的头节点。
示例 1：
输入：
head = [1,1,1,2,3,3,4]
输出：[1,3]
解释： 链表用从头到尾的值序列表示。1 和 3 都重复出现，各保留一次；2 和 4 只出现一次，删除。
示例 2：
输入：
head = [1,2,3]
输出：[]
解释： 所有值只出现一次，结果为空链表。
提示：
- 输入为非降序单链表。
- 结果只保留重复出现的值，每个值保留一个节点。
- 允许修改
next，返回新表头。
题意分析
本题只输出重复出现的值，每个值保留一次；只出现一次的值反而要删掉。有序性使同值节点构成连续段，因此逐段判断就能完成筛选，不需要哈希表。
解法：扫描等值段仅保留重复段首
核心思路
[!blue]
head是当前等值段的段首，next从它的原后继出发，越过所有同值节点后指向下一段。若head.next == next，说明没有额外的同值节点；不相等则说明当前段至少有两个节点。
tail始终指向已保留结果的尾节点。只有重复段才将段首接到tail后面，并推进tail，然后用已保存的next继续扫描。顺序按原链推进，所以结果仍然有序。最后必须令
tail.next = null，切断最后一个保留节点指向原链后续的旧连接。哑节点统一处理首段被删除和完全没有重复值的情况，返回dummy.next即可。
解题步骤
- 从段首向后跳过全部相同值，保存下一段入口。
- 段长至少为 2 时才把段首接入输出，单次值整段跳过。
- 全部段处理完后把输出尾 next 置空，返回新头。
代码实现
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class Solution {
public ListNode repeatedOnly(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (head != null) {
ListNode next = head.next;
while (next != null && next.val == head.val) {
next = next.next;
}
if (head.next != next) {
tail.next = head;
tail = head;
}
head = next;
}
tail.next = null;
return dummy.next;
}
}
type ListNode struct {
Val int
Next *ListNode
}
func repeatedOnly(head *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for head != nil {
next := head.Next
for next != nil && next.Val == head.Val {
next = next.Next
}
if head.Next != next {
tail.Next = head
tail = head
}
head = next
}
tail.Next = nil
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
相同值在有序链表中相邻，段首原后继是否等于下一段入口即可判断段长是否为 1。
易错点总结
[!yellow]
原题会保留只出现一次的值，本题恰好需要删掉这些值；不要误用删除整段重复值的逻辑。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 83. 删除排序链表中的重复元素 | 简单 | 原题每种值都留一个，本题只留下重复过的值。 |
| 82. 删除排序链表中的重复元素 II | 中等 | 原题删除全部重复段、只留单次值，本题恰好选择重复段并各留一个。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！