Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：83. Remove Duplicates From Sorted List（刪除排序鏈表中的重複元素）

掌握鏈表操作的基本功：如何優雅地刪除重複節點

luk 收錄於 Leetcode
 約 1300 字 預計閱讀 6 分鐘 

LeetCode 解題思路：Remove Duplicates from Sorted List（刪除排序鏈表中的重複元素）

題目描述

給定一個已排序的鏈表的頭節點 head，刪除所有重複的元素，使每個元素只出現一次。返回已排序的鏈表。

範例

範例 1：

輸入：head = [1,1,2]
輸出：[1,2]

視覺化：
1 → 1 → 2 → null
    ↓
1 → 2 → null

範例 2：

輸入：head = [1,1,2,3,3]
輸出：[1,2,3]

視覺化：
1 → 1 → 2 → 3 → 3 → null
    ↓
1 → 2 → 3 → null

限制條件

  • 鏈表中的節點數在範圍 [0, 300] 內
  • -100 <= Node.val <= 100
  • 題目保證鏈表是按升序排列的

核心概念

1. 問題本質分析

關鍵觀察：

  • 已排序：相同的元素一定相鄰
  • 刪除重複：保留第一個，刪除後續重複的
  • 原地修改：不需要創建新鏈表

2. 鏈表節點定義 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

3. 視覺化理解刪除過程 

原始鏈表：1 → 1 → 1 → 2 → 3 → 3 → null
         ↑
       current

步驟 1：發現重複
current.val (1) == current.next.val (1)
刪除：1 → 1 → 2 → 3 → 3 → null
      ↑   ↓
    current

步驟 2：還是重複
current.val (1) == current.next.val (1)
刪除：1 → 2 → 3 → 3 → null
      ↑
    current

步驟 3：不重複，移動指標
1 → 2 → 3 → 3 → null
    ↑
  current

繼續處理...

解法一：單指標遍歷（推薦）

思路

使用一個指標遍歷鏈表，當發現當前節點與下一個節點值相同時，跳過下一個節點。

程式碼實現 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 處理空鏈表
        if not head:
            return head
        
        # 從頭節點開始遍歷
        current = head
        
        while current and current.next:
            if current.val == current.next.val:
                # 發現重複，刪除下一個節點
                current.next = current.next.next
            else:
                # 沒有重複，移動到下一個節點
                current = current.next
        
        return head

執行過程詳解 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    """
    示例：[1,1,2,3,3]
    """
    if not head:
        return head
    
    current = head  # current 指向 1
    
    # 第一次循環
    # current.val = 1, current.next.val = 1
    # 1 == 1，刪除重複
    # 1 → 2 → 3 → 3
    # ↑
    # current 保持不動
    
    # 第二次循環
    # current.val = 1, current.next.val = 2
    # 1 != 2，移動指標
    # 1 → 2 → 3 → 3
    #     ↑
    #   current
    
    # 第三次循環
    # current.val = 2, current.next.val = 3
    # 2 != 3，移動指標
    # 1 → 2 → 3 → 3
    #         ↑
    #       current
    
    # 第四次循環
    # current.val = 3, current.next.val = 3
    # 3 == 3，刪除重複
    # 1 → 2 → 3
    #         ↑
    #       current
    
    # current.next = None，結束循環
    
    return head  # [1,2,3]

解法二：雙指標法（另一種思路）

思路

使用兩個指標：慢指標指向去重後的最後一個節點，快指標用於尋找下一個不同的值。

程式碼實現 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        slow = head
        fast = head.next
        
        while fast:
            if slow.val != fast.val:
                # 發現不同的值，連接並移動慢指標
                slow.next = fast
                slow = slow.next
            fast = fast.next
        
        # 斷開最後的連接
        slow.next = None
        
        return head

視覺化雙指標過程 

初始：1 → 1 → 2 → 3 → 3
     ↑   ↑
    slow fast

步驟 1：slow.val (1) == fast.val (1)
只移動 fast
1 → 1 → 2 → 3 → 3
↑       ↑
slow   fast

步驟 2：slow.val (1) != fast.val (2)
連接並移動 slow
1 → 2 → 3 → 3
    ↑   ↑
   slow fast

繼續處理...

解法三：遞迴解法（優雅但空間複雜度高）

思路

遞迴處理鏈表，先處理後面的部分，再處理當前節點。

程式碼實現 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 基礎情況
        if not head or not head.next:
            return head
        
        # 遞迴處理後續鏈表
        head.next = self.deleteDuplicates(head.next)
        
        # 如果當前節點與下一個節點重複，返回下一個節點
        if head.val == head.next.val:
            return head.next
        else:
            return head

遞迴過程分析 

deleteDuplicates([1,1,2])
├─ deleteDuplicates([1,2])
│  ├─ deleteDuplicates([2])
│  │  └─ 返回 [2] (基礎情況)
│  ├─ head.next = [2]
│  └─ 1 != 2，返回 [1,2]
├─ head.next = [1,2]
└─ 1 == 1，返回 [1,2] (跳過第一個1)

解法四：使用虛擬頭節點（處理邊界情況）

思路

添加虛擬頭節點簡化邊界處理。

程式碼實現 

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 創建虛擬頭節點
        dummy = ListNode(float('-inf'))
        dummy.next = head
        
        current = dummy
        
        while current.next:
            # 檢查是否需要刪除節點
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy.next

變化題型

1. 刪除所有重複元素（一個都不留） 

def deleteDuplicates2(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    [1,2,3,3,4,4,5] → [1,2,5]
    所有出現重複的元素都刪除
    """
    dummy = ListNode(0)
    dummy.next = head
    
    prev = dummy
    
    while head:
        # 檢查是否有重複
        if head.next and head.val == head.next.val:
            # 跳過所有重複元素
            val = head.val
            while head and head.val == val:
                head = head.next
            prev.next = head
        else:
            prev = head
            head = head.next
    
    return dummy.next

2. 保留最多 k 個重複 

def deleteDuplicatesK(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    """
    保留最多 k 個重複元素
    """
    if not head or k <= 0:
        return None
    
    current = head
    
    while current:
        # 計算重複次數
        count = 1
        runner = current
        
        while runner.next and runner.val == runner.next.val:
            count += 1
            if count > k:
                # 刪除多餘的重複
                runner.next = runner.next.next
            else:
                runner = runner.next
        
        current = runner.next
    
    return head

3. 返回重複的值列表 

def findDuplicates(head: Optional[ListNode]) -> List[int]:
    """
    返回所有重複出現的值
    """
    if not head:
        return []
    
    duplicates = []
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            if not duplicates or duplicates[-1] != current.val:
                duplicates.append(current.val)
        current = current.next
    
    return duplicates

4. 原地去重並返回新長度 

def removeDuplicatesLength(head: Optional[ListNode]) -> int:
    """
    去重並返回新鏈表的長度
    """
    if not head:
        return 0
    
    length = 1
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next
            length += 1
    
    return length

常見錯誤與陷阱

錯誤 1：忘記處理空鏈表 

# ❌ 錯誤！沒有檢查 head 是否為 None
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    current = head
    while current.next:  # 如果 head 是 None，會報錯
        # ...

正確做法：

# ✅ 正確處理空鏈表
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head
    # ...

錯誤 2：刪除節點後立即移動指標 

# ❌ 錯誤！可能會跳過連續的重複元素
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    current = head
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
            current = current.next  # 不應該移動！
        else:
            current = current.next

錯誤 3：沒有正確處理尾部 

# ❌ 錯誤！可能導致無限循環
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    current = head
    while current:  # 應該檢查 current.next
        if current.val == current.next.val:  # current.next 可能是 None
            current.next = current.next.next

錯誤 4：修改了原始鏈表結構 

# ❌ 如果需要保留原鏈表，這樣會破壞它
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 直接修改原鏈表
    # 應該考慮是否需要創建副本

複雜度分析

時間複雜度

  • 單指標遍歷：O(n)，只需遍歷一次
  • 雙指標法：O(n)，快指標遍歷所有節點
  • 遞迴解法：O(n)，訪問每個節點一次

空間複雜度

  • 單指標遍歷：O(1)，只使用常數額外空間
  • 雙指標法：O(1)，只使用兩個指標
  • 遞迴解法：O(n)，遞迴調用棧的深度

相關題目推薦

  1. LeetCode 82: Remove Duplicates from Sorted List II - 刪除所有重複元素
  2. LeetCode 203: Remove Linked List Elements - 移除特定值的節點
  3. LeetCode 237: Delete Node in a Linked List - 刪除鏈表中的節點
  4. LeetCode 19: Remove Nth Node From End of List - 刪除倒數第 N 個節點
  5. LeetCode 26: Remove Duplicates from Sorted Array - 陣列版本的去重
  6. LeetCode 1836: Remove Duplicates From an Unsorted Linked List - 未排序鏈表去重

實戰技巧總結

1. 鏈表操作模板 

# 遍歷鏈表
current = head
while current:
    # 處理當前節點
    process(current)
    current = current.next

# 刪除節點
if need_to_delete:
    current.next = current.next.next
else:
    current = current.next

2. 虛擬頭節點技巧 

# 簡化邊界處理
dummy = ListNode(0)
dummy.next = head
# 操作...
return dummy.next

3. 調試技巧 

def printList(head: Optional[ListNode]) -> None:
    """打印鏈表用於調試"""
    values = []
    current = head
    while current:
        values.append(str(current.val))
        current = current.next
    print(" → ".join(values) + " → null")

# 使用方式
print("處理前：", end="")
printList(head)
result = deleteDuplicates(head)
print("處理後：", end="")
printList(result)

4. 完整測試用例 

def test_deleteDuplicates():
    # 測試用例生成器
    def createList(values):
        if not values:
            return None
        head = ListNode(values[0])
        current = head
        for val in values[1:]:
            current.next = ListNode(val)
            current = current.next
        return head
    
    # 測試用例
    test_cases = [
        ([], []),
        ([1], [1]),
        ([1,1], [1]),
        ([1,1,1], [1]),
        ([1,1,2], [1,2]),
        ([1,1,2,3,3], [1,2,3]),
        ([1,2,3,3,4,4,5], [1,2,3,4,5]),
        ([1,1,1,2,2,3], [1,2,3]),
        ([0,0,0,0], [0])
    ]
    
    solution = Solution()
    for input_vals, expected in test_cases:
        head = createList(input_vals)
        result = solution.deleteDuplicates(head)
        # 驗證結果
        print(f"輸入: {input_vals} → 輸出: {listToArray(result)}")

進階思考

1. 如何處理循環鏈表？ 

def deleteDuplicatesCircular(head: Optional[ListNode]) -> Optional[ListNode]:
    """處理循環鏈表的去重"""
    if not head or head.next == head:
        return head
    
    current = head
    
    # 使用 do-while 邏輯
    while True:
        if current.val == current.next.val:
            current.next = current.next.next
            if current.next == head and current.val == head.val:
                # 特殊處理頭尾相同的情況
                head = head.next
        else:
            current = current.next
        
        if current.next == head:
            break
    
    return head

2. 如何在 O(1) 空間內去重未排序鏈表？ 

def deleteDuplicatesUnsorted(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    挑戰：不使用額外空間去重未排序鏈表
    時間複雜度會是 O(n²)
    """
    current = head
    
    while current:
        runner = current
        while runner.next:
            if runner.next.val == current.val:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next
    
    return head

3. 如何統計刪除的節點數？ 

def deleteDuplicatesCount(head: Optional[ListNode]) -> Tuple[Optional[ListNode], int]:
    """返回去重後的鏈表和刪除的節點數"""
    if not head:
        return head, 0
    
    count = 0
    current = head
    
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
            count += 1
        else:
            current = current.next
    
    return head, count

總結

刪除排序鏈表中的重複元素是鏈表操作的基礎題，透過這題可以學到：

  1. 鏈表基本操作：遍歷、刪除節點
  2. 指標操作技巧：何時移動、何時保持
  3. 邊界條件處理：空鏈表、單節點、全重複
  4. 算法思維：利用「已排序」特性簡化問題
  5. 代碼優化：從暴力解到優雅解

關鍵要點：

  • 利用已排序特性：相同元素必相鄰
  • 刪除節點時注意指標移動
  • 處理好邊界條件
  • 理解原地修改的含義

練習建議

  1. 基礎練習：

    • 手動畫圖模擬刪除過程
    • 實現不同的解法並比較
    • 處理各種邊界情況

  2. 進階練習：

    • 嘗試刪除所有重複（進階版）
    • 實現未排序鏈表去重
    • 添加更多功能（計數、反轉等）

  3. 綜合應用：

    • 結合其他鏈表操作
    • 在實際項目中應用
    • 優化空間和時間複雜度

記住：鏈表操作的關鍵是細心處理指標，畫圖是最好的輔助工具！

更新於 2024-12-02 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmLinked-ListTwo-Pointers
返回 | 主頁
0%