給定一個鏈結串列的頭節點
head和一個整數val，移除所有值等於val的節點，回傳新的頭節點。
Example:
Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]
Intuition
TIP
核心思路：使用 dummy head 簡化頭節點可能被刪除的邊界情況，遍歷時跳過值等於 val 的節點。
- 頭節點本身可能需要被刪除，使用 dummy head 可以統一處理
- 遍歷鏈結串列，當下一個節點的值等於 val 時，將 next 指向再下一個節點
Approaches
1. Recursive — O(n) / O(n)
- Idea: 遞迴處理子問題，若當前節點值等於 val 則跳過，否則保留並連接後續結果
- Time:
O(n) - Space:
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 — O(n) / O(1)
- Idea: 建立 dummy 節點指向 head，遍歷時如果 next 節點的值等於 val 就跳過
- Time:
O(n) - Space:
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 技巧適用於所有可能修改頭節點的鏈結串列操作
- Key trick: 刪除節點時注意不要移動 curr 指針，因為新的 next 節點可能也需要被刪除