# 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. 遍歷鏈表,直到 current
或 current.next
為 None
:
- 如果 current.val == current.next.val
,則跳過 current.next
,直接讓 current.next
指向 current.next.next
。
- 否則,移動 current
到 current.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.val
或 head.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. 使用兩個指針 prev
和 current
,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. 考慮邊界條件,如空鏈表或全重復鏈表。
掌握這個問題不僅有助于理解鏈表的基本操作,還能為更復雜的鏈表問題打下基礎。建議讀者在理解后嘗試解決其變種問題,如刪除所有重復元素的版本,以加深對鏈表操作的理解。
”`
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。