刪除排序鏈表中的重復元素 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和下一個有效節點

這是處理鏈表刪除問題的經典模式，特別適用于需要刪除多個連續節點的場景！