題目描述:給定一個鏈結串列的頭節點 head 和一個整數 val,移除所有值等於 val 的節點,返回新的頭節點。
解題思路:使用**虛擬頭節點(dummy head)**技巧,可以統一處理頭節點和中間節點的刪除,避免特判頭節點。
建立一個 dummy 節點,令 dummy->next = head,然後用 curr 指標從 dummy 開始迭代。若 curr->next->val == val,則將 curr->next 跳過(curr->next = curr->next->next);否則移動 curr = curr->next。最終返回 dummy->next 作為新頭節點。這個方式使刪除頭節點與刪除其他節點的邏輯完全一致,程式碼簡潔且不易出錯。
時間複雜度:O(n) — 每個節點最多被訪問一次,n 為鏈結串列的節點總數。
空間複雜度:O(1) — 只使用常數個額外指標(dummy、curr),不需要額外的資料結構。
1. Create dummy node with dummy.next = head
2. Set curr = dummy
3. While curr.next is not null:
a. If curr.next.val == val:
- curr.next = curr.next.next (skip the node)
b. Else:
- curr = curr.next
4. Return dummy.next方法一:遞迴
removeElements(head, val) 先遞迴處理 head->next,若當前節點值等於 val 則直接返回遞迴結果(跳過當前節點),否則令 head->next = 遞迴結果 後返回 head。程式碼極簡,時間複雜度 O(n),但空間複雜度為 O(n)(遞迴呼叫堆疊深度等於串列長度),在串列很長時有堆疊溢位風險。
方法二:不使用 dummy 的直接迭代
先單獨處理頭部:用 while 迴圈跳過所有值為 val 的頭節點,更新 head;再用 prev/curr 雙指標迭代刪除中間節點。邏輯正確但需要分兩段處理,程式碼較冗長,相比 dummy 方法更易出錯。
val 的節點,而不是等於,程式碼需要如何修改?整體複雜度是否改變?delete),需要注意什麼?直接 curr->next = curr->next->next 而不 delete 會造成什麼問題?