Description
給定一個鏈結串列的頭節點
head和一個整數val，移除所有值等於val的節點，回傳新的頭節點。
Example:
Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]
Intuition#
核心思路：使用 dummy head 簡化頭節點可能被刪除的邊界情況，遍歷時跳過值等於 val 的節點。
- 頭節點本身可能需要被刪除，使用 dummy head 可以統一處理
- 遍歷鏈結串列，當下一個節點的值等於 val 時，將 next 指向再下一個節點
Approaches#
1: Recursive#
- 概念: 遞迴處理子問題，若當前節點值等於 val 則跳過，否則保留並連接後續結果
- 時間複雜度:
O(n) - 空間複雜度:
O(n)- 遞迴堆疊
class Solution {
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
if (head == null) return null
head.next = removeElements(head.next, `val`)
return if (head.`val` == `val`) head.next else head
}
}⭐2: Iterative with Dummy Head#
- 概念: 建立 dummy 節點指向 head，遍歷時如果 next 節點的值等於 val 就跳過
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var curr: ListNode? = dummy
while (curr?.next != null) {
if (curr.next!!.`val` == `val`) {
curr.next = curr.next!!.next
} else {
curr = curr.next
}
}
return dummy.next
}
}🔑 Takeaways#
- Pattern: Dummy head 技巧適用於所有可能修改頭節點的鏈結串列操作
- 關鍵技巧: 刪除節點時注意不要移動 curr 指針，因為新的 next 節點可能也需要被刪除