# 203. Remove Linked List Elements ## [題目](https://leetcode.com/problems/remove-linked-list-elements/description/?envType=problem-list-v2&envId=linked-list) ## 演算法 ``` 1. 設定一個dummy node，它的next指向head，再讓node指向dummy; 2. 當node下一點不為nullptr: 2.1 若node下一點的值 == val，將garbage指向node下一點，node的next指向下下點，刪除garbage 2.2 否則，node = node->next 3. return dummy->next ``` ## 演算法正確性證明 循環不變式：在每次迴圈執行前，node以前的點(包含node)，它的值不為val ```初始```：一開始node會指向dummy，只有dummy這個點，它的值不為val，命題成立。 ```維持```：若```node下一點的值 == val```，演算法僅會將node的下一點移除，再進行下一次的迭代，因此命題仍然成立；若```node下一點的值 != val```，演算法會讓node往下一個點前進，但判斷是已經保證下一個點 != val，因此命題仍然成立。 ```終止```：在迴圈內，要嘛移除node的下一點，要嘛讓node往下一個點前進，所有最後node下一點最後必為nullptr，根據命題，此時整條鏈結串列都不包含val，完成證明。 ## 程式碼 ```cpp= /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy = new ListNode(-1); dummy -> next = head; ListNode* node = dummy; while (node -> next) { if (node -> next -> val == val) { ListNode* garbage = node -> next; node -> next = node -> next -> next; delete garbage; } else { node = node -> next; } } return dummy -> next; } }; ```