203.移除鏈表元素：

給你一個鏈表的頭節(jié)點 head 和一個整數 val 高氮，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點，并返回 新的頭節(jié)點 顷牌。

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1
輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7
輸出：[]

提示：

• 列表中的節(jié)點數目在范圍 [0, 104] 內
• 1 <= Node.val <= 50
• 0 <= val <= 50

題目鏈接

思考：

本題是一道經典的對鏈表這種數據結構的考察剪芍，主要考察了對鏈表中元素刪除的操作。刪除某個節(jié)點窟蓝，其實只需要將上個節(jié)點指向該結點的下個結點即可罪裹。在c語言中需要將被刪除的結點進行釋放操作。

需要特別注意的是运挫，刪除頭指針的方式和非頭指針的方式是有所不同的状共，因為頭指針的前面是沒有上一個節(jié)點的。

保留頭指針：

將頭結點和其他節(jié)點分開來討論谁帕，寫出兩種不同的刪除方式峡继。

/**
 * 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) {
       //delete head;
       while (head != NULL && head->val==val)
       {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
       }
       //delete other nodes;
       ListNode* cur=head;//將cur指向頭指針開始遍歷
       while(cur!=NULL && cur->next!=NULL)
       {
        if (cur->next->val == val) { //實際操作刪除修改的是cur->next即cur后一個元素
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
       }
       return head;
    }
};

虛擬頭結點：

我們還可以通過創(chuàng)建虛擬頭結點的方式，在原來的頭結點前再另加一個新頭結點匈挖，原來的頭結點就變成了第二個結點碾牌，這樣的話颠猴，對于所有的結點都可以使用同一種刪除方式。

/**
 * 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* newHead = new ListNode(0);//設置虛擬頭結點
        newHead->next = head;//原來的頭結點稱為第二位
        ListNode* cur = newHead;//剩下的操作只需考慮一種刪除
        while (cur->next != NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else {
                cur = cur->next;
            }
        }
        head = newHead->next;//還原頭結點
        delete newHead;
        return head;
    }
};

往期回顧：
LeetCode54. 螺旋矩陣
LeetCode59.螺旋矩陣II
LeetCode977.有序數組的平方
LeetCode844.比較含退格的字符串
LeetCode283.移動零
LeetCode27.移除元素
LeetCode26.刪除有序數組中的重復項
LeetCode209.長度最小的子數組
LeetCode904. 水果成籃
LeetCode242.有效的字母異位詞
LeetCode76.最小覆蓋子串