題目網址：https://leetcode.cn/problems/remove-linked-list-elements

題意：給一整數 val, 刪除 linked list 中所有 node.val == val 的 node。

Solution：

想法：用 dummy 來指向 head, pre 則記住當前 node 的前一個 node
初始化 pre 為 dummy(head 的前一個 node)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // dummy 指向 link-list 之 head
        const ListNode *dummy = new ListNode(0, head);
        ListNode *curr = head, *prev = dummy;

        while (curr) {
            if (curr->val == val) { // 當前 node 要刪除
                prev->next = curr->next;
            } else { // 不刪除, 往下一個 node 前進, current node 變成前一個 node
                prev = curr;
            }

            curr = curr->next;
        }

        return dummy->next;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需要常數空間