链表中等1 种解法
#82删除排序链表中的重复元素 II
删除有序链表中所有出现过重复的值，只保留从未重复的节点。
#链表#双指针
原题
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
解题主线
- 有序性使相同值连续出现，只需识别并跳过整段重复值。
- 头节点也可能属于重复段，因此必须使用虚拟头节点。
解法 1：虚拟头节点跳过重复段
prev 指向已确认保留部分的尾部；若 prev.next 与其后继同值，就跳过这一值的全部节点。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode deleteDuplicates(ListNode head) {
// 虚拟头节点让头部重复段与中间重复段使用同一套删除逻辑。
ListNode dummy = new ListNode(0, head);
// prev 始终指向已经确认保留部分的最后一个节点。
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
if (prev.next.val != prev.next.next.val) {
prev = prev.next;
continue;
}
int duplicate = prev.next.val;
// 删除整段重复值后 prev 不前进，以便继续检查新接上的下一段。
while (prev.next != null && prev.next.val == duplicate) {
prev.next = prev.next.next;
}
}
return dummy.next;
}
}边界与易错点
- 不要与第 83 题混淆：本题不是每组保留一个，而是整组删除。
- 跳过重复段后 prev 不应前进，它仍可能需要连接下一段。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q082_linkedList_delDuplicates.java