删除排序链表中的重复元素 II

题目描述

给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字。

示例

示例1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
解释：3和4都出现了重复，所以要全部删除示例2：
输入：head = [1,1,1,2,3]  
输出：[2,3]
解释：1出现了重复，所以要全部删除

核心思想

与删除重复元素I不同，这里要求完全删除重复的节点，而不是保留一个。

关键技巧：

1. 虚拟头节点：因为头节点也可能被删除
2. 双指针：prev 指向最后一个确定保留的节点，curr 用于遍历
3. 跳过重复：发现重复时，跳过所有相同值的节点

最优雅解法

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {public ListNode deleteDuplicates(ListNode head) {// 创建虚拟头节点，简化边界处理ListNode dummy = new ListNode(0);dummy.next = head;// prev：指向最后一个确定保留的节点// curr：用于遍历的当前节点ListNode prev = dummy;ListNode curr = head;while (curr != null) {// 检查是否有重复：curr和curr.next值相同if (curr.next != null && curr.val == curr.next.val) {int duplicateVal = curr.val;// 跳过所有值为duplicateVal的节点while (curr != null && curr.val == duplicateVal) {curr = curr.next;}// 连接prev和curr，删除所有重复节点prev.next = curr;} else {// 当前节点无重复，prev前进prev = curr;curr = curr.next;}}return dummy.next;}
}

算法步骤详解

示例1演示：[1,2,3,3,4,4,5]

初始状态：
dummy → 1 → 2 → 3 → 3 → 4 → 4 → 5 → null↑      ↑
prev   curr步骤1：检查curr(1)和curr.next(2)
1 ≠ 2，无重复
prev = curr = 1, curr = 2dummy → 1 → 2 → 3 → 3 → 4 → 4 → 5 → null↑   ↑prev curr步骤2：检查curr(2)和curr.next(3)  
2 ≠ 3，无重复
prev = curr = 2, curr = 3dummy → 1 → 2 → 3 → 3 → 4 → 4 → 5 → null↑   ↑prev curr步骤3：检查curr(3)和curr.next(3)
3 = 3，发现重复！
duplicateVal = 3
跳过所有值为3的节点：curr = 4dummy → 1 → 2 → 3 → 3 → 4 → 4 → 5 → null↑           ↑prev        curr连接：prev.next = curr
dummy → 1 → 2 ─────────→ 4 → 4 → 5 → null↑           ↑prev        curr步骤4：检查curr(4)和curr.next(4)
4 = 4，发现重复！
duplicateVal = 4  
跳过所有值为4的节点：curr = 5dummy → 1 → 2 ─────────→ 5 → null↑           ↑prev        curr连接：prev.next = curr
dummy → 1 → 2 ────────→ 5 → null↑          ↑prev       curr步骤5：检查curr(5)和curr.next(null)
curr.next = null，无重复
prev = curr = 5, curr = null最终结果：[1,2,5]

关键理解点

1. 虚拟头节点的作用

ListNode dummy = new ListNode(0);
dummy.next = head;

• 简化边界处理，避免特殊判断头节点
• 保证 prev 始终有效

2. 重复检测逻辑

if (curr.next != null && curr.val == curr.next.val) {// 发现重复
}

• 通过比较相邻节点检测重复
• 由于链表已排序，重复元素必然相邻

3. 完全删除重复节点

int duplicateVal = curr.val;
while (curr != null && curr.val == duplicateVal) {curr = curr.next;  // 跳过所有重复值
}
prev.next = curr;  // 连接到下一个不重复的节点

• 记录重复值，跳过所有相同值的节点
• 直接连接 prev 和第一个不重复的节点

边界情况处理

情况1：空链表

head = null
return dummy.next = null ✓

情况2：单节点

head = [1]
curr.next = null，不进入重复检测
return [1] ✓

情况3：全部重复

head = [1,1,1]
全部删除，prev.next = null
return [] ✓

情况4：头节点重复

head = [1,1,2,3]
虚拟头节点确保正确处理
return [2,3] ✓

复杂度分析

• 时间复杂度：O(n)
  • 每个节点最多被访问2次（检测+跳过）
• 空间复杂度：O(1)
  • 只使用了常数个指针变量

常见错误

1. 忘记虚拟头节点

// 错误：头节点重复时处理复杂
ListNode prev = null;
if (head.val == head.next.val) {// 复杂的头节点删除逻辑...
}

2. 重复删除不完全

// 错误：只删除一个重复节点
if (curr.val == curr.next.val) {curr.next = curr.next.next;  // 只删除一个
}

3. 指针更新错误

// 错误：在删除重复节点后错误更新prev
prev.next = curr;
prev = curr;  // 错误！curr指向被删除的节点

总结

这个算法的精髓在于：

1. 虚拟头节点 简化边界处理
2. 双指针技巧 保持连接关系
3. 完全跳过 所有重复值的节点
4. 正确连接 prev和下一个有效节点

这是处理链表删除问题的经典模式，特别适用于需要删除多个连续节点的场景！