DSA 練功筆記 (19)：Remove Linked List Elements

Topics: Linked List. LeetCode 203.

理解題目

給你一個 Linked List 的頭 head 還有一個 int 值 val ，然後把這個 Linked List 裡面的值等於 val 的節點移除掉，完成後回傳新的 Linked List。

Example 1:

Input: head = [1,2,6,3,4,5,6] Output: [1,2,3,4,5]

Example 2:

Input: head = [] Output: []

題目限制

Linked List 的節點數量在 0 ~ 10⁴ 之間

Node.val 的值在 1 ~ 50 的區間，要移除的值 val 在 0 ~ 50 間

思路與解法

新增、移除 Linked List 中的節點就是改變前一個節點或者是目前節點中帶有下一個節點的位址，不過比較特別的是 Head 節點沒有前一個節點的位址可以更改，所以第一步可以先把 Head 節點的情況處理掉，只要開頭節點的值等於 val 就把 head 指向下一個節點，這樣就移除掉了開頭節點：

for head != nil && head.Val == val {
    head = head.Next
}

再來可以考慮如果 head 為空的情況，就直接回傳空的 list：

if head == nil {
    return head
}

因為從左到右走訪 list，第一個走訪的節點一定是頭節點，把開頭節點的值等於 val 跟空節點的情況處理掉後，接下來節點的值一定不等於 val，也就是最後答案新的 Linked List 的開頭節點，所以只要這個新的開頭節點的下一個位址不為空，我們就能一個一個判斷直到整個 list 走完，這邊會使用 Two Pointers 來走訪目前節點的位址和更改節點指向的新位址：

previous := head
current := head.Next
for current != nil {
    if current.Val == val {
        previous.Next = current.Next
    } else {
        previous = current
    }
    current = current.Next
}
return head

走訪 list 過程中碰到想移除的節點要如何移掉？這是一開始想的時候卡住的地方，分析了答案後發現可以用一個 pointer previous 來代表開頭節點，另一個 pointer current 來代表下一個節點，也可以說是目前 list 的結束位置節點，只要有下一個節點位址 (不為空) 就代表還沒走完 list。

所以當目前節點的值等於 val 我們就可以把 previous 節點的下一個位址移到 current 指向的下個節點表示刪除了 current node，否則只要移動 previous 目前指向的位址到 current 的位址，表示這個節點我們要保留，繼續往下個點走訪。每一次判斷節點的值相同或不同後，都要記得把 current 的位址移到 current 指向的下個節點位址，因為不管是刪除或者是保留 current 節點，current 節點都不是 list 目前的尾巴了，要繼續向前走訪確 list 是不是還有節點還沒走完，完整的 code 如下：

func RemoveElements(head *ListNode, val int) *ListNode {
    // Remove the head node where the value is equal to the val.
    for head != nil && head.Val == val {
        head = head.Next
    }
    if head == nil {
        return head
    }
    // In this step, we ensure the following head.val is not equal to the val.
    // Set up two pointers that can track the position and address of the node during the
    // following node traversal.
    previous := head
    current := head.Next
    // Move two pointers previous and current until current's next is nil.
    for current != nil {
        // Drop current node by changing the previous node's link to the current node's next address
        // if current value is equal to val. Otherwise, move previous forward to current.
        if current.Val == val {
            previous.Next = current.Next
        } else {
            previous = current
        }
        // In the end of traversal, move current address to the next node.
        current = current.Next
    }
    return head
}

Big O notation

• Time Complexity: O(n), because this function traverses the entire linked list head where the length depends on the number of values.
• Space Complexity: O(1), this function didn’t use any extra space that depends on any size of input argument.

Note

雖然 Linked List 的概念大致上都了解，不過第一次做這類型的題目連輸入的 head 為什麼是 Linked List，實際的數據結構長什麼樣子，以及怎麼去操作 List 都還要畫圖想一下，Coding 還是要動手做做看才行。

Reference

1. 203.移除鍊錶元素