溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

LeetCode怎樣刪除排序鏈表中的重復元素

發布時間:2021-12-15 14:53:34 來源:億速云 閱讀:132 作者:小新 欄目:大數據
# LeetCode怎樣刪除排序鏈表中的重復元素

## 問題概述

在LeetCode的鏈表問題中,"刪除排序鏈表中的重復元素"(Remove Duplicates from Sorted List)是一個經典的基礎題目。題目要求我們給定一個已排序的鏈表,刪除所有重復的元素,使得每個元素只出現一次。最終返回刪除后的鏈表。

### 題目描述
- **題目編號**:83
- **難度**:簡單
- **鏈接**:https://leetcode.com/problems/remove-duplicates-from-sorted-list/

**示例**:
```python
輸入: 1->1->2
輸出: 1->2

輸入: 1->1->2->3->3
輸出: 1->2->3

理解題目

首先,我們需要明確幾個關鍵點: 1. 鏈表已排序:這意味著所有重復的元素都是相鄰的,這大大簡化了問題。 2. 刪除重復元素:我們需要保留每個元素的一個實例,而不是全部刪除。 3. 返回修改后的鏈表:我們需要在原鏈表上進行修改,而不是創建一個新的鏈表。

解題思路

方法一:直接遍歷法

這是最直觀的解法。我們可以遍歷鏈表,比較當前節點和下一個節點的值。如果相同,就跳過下一個節點;如果不同,就繼續遍歷。

步驟: 1. 初始化一個指針 current 指向鏈表的頭節點。 2. 遍歷鏈表,直到 currentcurrent.nextNone: - 如果 current.val == current.next.val,則跳過 current.next,直接讓 current.next 指向 current.next.next。 - 否則,移動 currentcurrent.next。 3. 返回頭節點。

代碼實現(Python)

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

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    while current and current.next:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next
    return head

時間復雜度:O(n),其中 n 是鏈表的長度。我們只需要遍歷一次鏈表。 空間復雜度:O(1),沒有使用額外的空間。

方法二:遞歸法

雖然遞歸法在空間復雜度上不如直接遍歷法高效,但它提供了一種更簡潔的思考方式。

思路: 1. 如果鏈表為空或只有一個節點,直接返回鏈表。 2. 遞歸處理 head.next。 3. 如果 head.val == head.next.val,則跳過 head.next,直接返回 head。 4. 否則,返回 head。

代碼實現(Python)

def deleteDuplicates(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    head.next = deleteDuplicates(head.next)
    return head.next if head.val == head.next.val else head

時間復雜度:O(n),遞歸深度為鏈表長度。 空間復雜度:O(n),遞歸調用棧的空間。

邊界條件與測試用例

為了確保代碼的正確性,我們需要考慮以下邊界條件: 1. 空鏈表:輸入為 None,應返回 None。 2. 單節點鏈表:輸入為 1->None,應返回原鏈表。 3. 全重復鏈表:輸入為 1->1->1->None,應返回 1->None。 4. 無重復鏈表:輸入為 1->2->3->None,應返回原鏈表。

測試用例示例

# 測試用例1:空鏈表
assert deleteDuplicates(None) is None

# 測試用例2:單節點鏈表
head = ListNode(1)
assert deleteDuplicates(head) == head

# 測試用例3:全重復鏈表
head = ListNode(1, ListNode(1, ListNode(1)))
result = deleteDuplicates(head)
assert result.val == 1 and result.next is None

# 測試用例4:無重復鏈表
head = ListNode(1, ListNode(2, ListNode(3)))
result = deleteDuplicates(head)
assert result.val == 1 and result.next.val == 2 and result.next.next.val == 3

常見錯誤與陷阱

在解決這個問題時,初學者可能會遇到以下錯誤: 1. 未處理空鏈表:直接訪問 head.valhead.next 會導致 AttributeError。 2. 指針移動邏輯錯誤:在發現重復時,忘記移動指針或錯誤地移動指針。 3. 修改鏈表后未返回頭節點:在修改鏈表后,需要返回鏈表的頭節點。

錯誤示例

def deleteDuplicates(head: ListNode) -> ListNode:
    current = head
    while current.next:  # 錯誤:未檢查 current 是否為 None
        if current.val == current.next.val:
            current.next = current.next.next
        current = current.next  # 錯誤:在跳過節點后未檢查 current.next
    return head

擴展問題

問題變種:刪除所有重復元素

LeetCode中還有一個類似的問題(第82題),要求刪除所有重復的元素,包括唯一的元素。例如:

輸入: 1->1->2->3->3
輸出: 2

解法思路: 1. 使用一個啞節點(dummy node)作為鏈表的起始節點,簡化頭節點的處理。 2. 使用兩個指針 prevcurrent,prev 指向當前不重復的節點,current 用于遍歷鏈表。 3. 當發現重復時,跳過所有重復節點。

代碼實現(Python)

def deleteAllDuplicates(head: ListNode) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    current = head
    while current:
        while current.next and current.val == current.next.val:
            current = current.next
        if prev.next == current:
            prev = prev.next
        else:
            prev.next = current.next
        current = current.next
    return dummy.next

總結

刪除排序鏈表中的重復元素是一個基礎的鏈表操作問題,通過直接遍歷法可以高效解決。關鍵點在于: 1. 利用鏈表已排序的特性,只需比較相鄰節點。 2. 注意指針的移動邏輯,避免空指針異常。 3. 考慮邊界條件,如空鏈表或全重復鏈表。

掌握這個問題不僅有助于理解鏈表的基本操作,還能為更復雜的鏈表問題打下基礎。建議讀者在理解后嘗試解決其變種問題,如刪除所有重復元素的版本,以加深對鏈表操作的理解。

參考資料

  1. LeetCode官方題解:https://leetcode.com/problems/remove-duplicates-from-sorted-list/solution/
  2. 《算法導論》中的鏈表章節。
  3. Python官方文檔關于鏈表的實現。

”`

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

亚洲午夜精品一区二区_中文无码日韩欧免_久久香蕉精品视频_欧美主播一区二区三区美女