題目描述:給定一個已排序的鏈結串列(Linked List)的頭節點 head,請刪除所有重複的節點,使每個值只出現一次,並回傳排序後的鏈結串列頭節點。
解題思路:由於串列已排序,所有重複的節點必然是相鄰的,因此不需要額外的雜湊表。使用一個指針 cur 從頭節點開始遍歷:每次檢查 cur->next 是否存在,且 cur->val == cur->next->val(即下一個節點是重複的)。若是,則執行 cur->next = cur->next->next(跳過重複節點,將其從鏈結串列中移除);若不是重複節點,則 cur = cur->next 前進到下一個不同值的節點。這樣當迴圈結束時,每個值只保留了第一次出現的節點。注意:在刪除重複節點時 cur 不移動,因為新的 cur->next 可能仍然重複。
時間複雜度:O(n) — 每個節點最多被訪問兩次(一次比較,一次被跳過),整體為線性掃描,n 為鏈結串列節點數。
空間複雜度:O(1) — 只使用一個額外指針 cur,原地修改鏈結串列,不需額外的記憶體空間。
1. Set cur = head
2. While cur is not null AND cur.next is not null:
a. If cur.val == cur.next.val:
- cur.next = cur.next.next (bypass the duplicate)
b. Else:
- cur = cur.next (advance to next distinct node)
3. Return head方法一:遞迴解法
對每個節點遞迴處理其後續子串列:deleteDuplicates(head->next) 先處理後半部分,回傳去重後的子串列頭;若 head->val == head->next->val,則回傳 head->next(跳過 head),否則回傳 head。遞迴寫法程式碼極為簡潔,但每個節點產生一層遞迴呼叫,空間複雜度為 O(n)(函式呼叫堆疊),在串列很長時有堆疊溢位的風險。
方法二:適用於「刪除所有出現過的重複值」變體(LeetCode 82) 若要求連重複元素的第一次出現也要刪除(82 題),需要使用**虛擬頭節點(Dummy Node)**技巧,並用雙指針分別指向「確定不重複的尾端」和「當前掃描位置」,偵測到重複值時跳過整個重複段落。此方法時間 O(n)、空間 O(1),但邏輯比 83 題複雜。
cur->next = cur->next->next),被跳過的節點在 C++ 中會造成記憶體洩漏(Memory Leak)。如果需要正確釋放記憶體,程式碼應如何修改?在 LeetCode 的評測環境下為何通常不需要擔心這個問題?