# 【LeetCode】203. Remove Linked List Elements

## Question link
[Link](https://leetcode.com/problems/remove-linked-list-elements/description/)

## Intuition
> Given the `head` of a linked list and an integer `val`, remove all the nodes of the linked list that has `Node.val == val`, and return _the new head_.
(給定一個鏈結串列與整數，移除掉所有鏈結串列中等於`val`的節點並回傳新的`head`)

:::info
題意要求移除掉`ListNode`的值符合`val`時要移除掉，也就是在遍歷過程中，如果遇到**下一個節點**是符合條件的，就將其跳過連接到下下一個節點。
1. Dummy Node Approach
* 為了避免需要處理掉如果一開始的`head->val`就等於`val`情況，我可以先創建虛擬節點或者又稱哨兵節點，來進行處理
2. Indirect Pointer Approach
* 使用間接指標來進操作每一個節點中的`next`指標，這樣就不需要額外的`dummy node`了，藉由改變指標(view-point)，來進行操作，view-point 指得是從操作`struct ListNode*` 變成操作其`next`的指標
[Linus Torvalds 在 TED 2016 的訪談](http://www.ted.com/talks/linus_torvalds_the_mind_behind_linux?language=zh-tw)
:::

## Approach
:::info
1. Dummy Node Approach
* 建立一個`dummy`，並進行初始化，將其 `next` 節點指向 `head`。
* 建立一個 `ptr` 指標作為遍歷時的操作指標，並將其指向`dummy`
* 迴圈遍歷整個鏈結串列，直到沒有下一個節點，也就是 `ptr->next` 為 `NULL`
* 檢查下個節點的值是否等於`val`，是則將`next`指向下下一個節點也就是`next->next`
* 否則更新 `ptr`，指向下一個節點
* 最後回傳 `dummy->next`
2. Indirect Pointer Approach
* 建立間接指標 `ptr` 指向 `head` 指標
* 迴圈遍歷，直到 `*ptr` 為空指標
* 如果`ptr`指標指向的指標中的值等於 `val`，就將其鏈接到下下一個指標
* 否則就更新`ptr`，將其指向`next`指標
* 最後直接回傳`head`
:::

:::success
在Indirect Pointer Approach中需要練習如何解讀指標的指標並進行操作
* `ptr` 為間接指標，其中儲存的值是指向指標的地址
* `*ptr` 為dereference間接指標，依照儲存的地址去取值，也就是取得其指向指標的值，其回傳型態為`struct ListNode*`
:::

## Complexity

- Time complexity: $O(n)$
- Space complexity: $O(1)$

## Code

### Solution 1

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;
    struct ListNode* ptr = dummy;
    while (ptr->next) { 
        if (ptr->next->val == val) {
            ptr->next = ptr->next->next;
        }
        else{
            ptr = ptr->next;
        }
    }
    struct ListNode* result = dummy->next;
    free(dummy);
    return result;
}

### Solution 2

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode **ptr = &head;
    while (*ptr){
        if ((*ptr)->val == val){
            *ptr = (*ptr)->next;
        }
        else {
            ptr = &(*ptr)->next;
        }
    }
    return head;
}