題目描述:給定一個已排序鏈結串列的頭節點 head,刪除所有含有重複數字的節點(只要某個值出現超過一次,就把所有具有該值的節點全部移除),並返回只保留唯一值的串列頭節點。
解題思路:
由於串列已排序,所有重複值的節點必定相鄰,因此可以用一個 prev 指標追蹤「目前確定保留的最後一個節點」,再用 cur 指標向前探索。
next 指向 head。這樣即使原始頭節點需要被刪除,也不需要特判。prev 始終指向最後一個「確定保留」的節點。cur 與 cur->next 的值相同,就繼續讓 cur 前進,直到 cur->next 不同或為空,此時整段 [原本的 cur, 現在的 cur] 都有重複,全部跳過:令 prev->next = cur->next。cur 與 cur->next 值不同,表示 cur 是唯一值,可以保留:將 prev 推進到 cur。dummy->next。時間複雜度:O(n) — 每個節點最多被 cur 指標走訪一次,整體為線性時間,n 為串列節點數。
空間複雜度:O(1) — 只使用常數個指標(dummy、prev、cur),不需要額外的雜湊表或陣列。
1. Create a dummy node with dummy.next = head.
2. Set prev = dummy, cur = head.
3. While cur is not null:
a. If cur.next exists and cur.val == cur.next.val:
- Advance cur forward until cur.next is null or cur.next.val != cur.val.
- Set prev.next = cur.next (skip the entire duplicate run).
b. Else:
- cur is unique; advance prev = cur.
c. Advance cur = cur.next.
4. Return dummy.next.方法一:遞迴
遞迴處理每個子問題:若當前節點的值與下一節點相同,則記錄重複值,跳過所有具有該值的節點後遞迴處理剩餘串列;否則直接令 head->next = deleteDuplicates(head->next) 並返回 head。時間複雜度 O(n),空間複雜度 O(n)(遞迴呼叫堆疊)。
方法二:雜湊表計數(兩次走訪)
第一次走訪用 unordered_map 統計每個值出現次數;第二次走訪重建串列,只保留計數為 1 的節點。時間複雜度 O(n),空間複雜度 O(n)。優點是邏輯最直觀,但不利用已排序特性,空間消耗較大。
prev 的推進邏輯會有什麼不同?