一、題目描述

刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

二、解題思路

解法1：

刪除結(jié)點(diǎn)的步驟
1. 找到該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
2. 進(jìn)行刪除操作
除頭結(jié)點(diǎn)時(shí)另做考慮（由于頭結(jié)點(diǎn)沒(méi)有前一個(gè)結(jié)點(diǎn)）

代碼實(shí)現(xiàn)

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != nullptr && head->val == val) {
            head = head->next;
        }

        if (head == nullptr) return head;
        ListNode *prev = head;
        // 確保當(dāng)前節(jié)點(diǎn)后還有節(jié)點(diǎn)
        while (prev->next != nullptr) {
            if (prev->next->val == val) {
                prev->next = prev->next->next;
            } else {
                prev = prev->next;
            }
        }
        return head;
    }
};

解法2：

避免分別處理頭結(jié)點(diǎn)和剩余節(jié)點(diǎn)，可以通過(guò)在頭結(jié)點(diǎn)前增加一個(gè)節(jié)點(diǎn)，統(tǒng)一操作

代碼實(shí)現(xiàn)：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != nullptr && head->val == val) {
            head = head->next;
        }

        if (head == nullptr) return head;
        ListNode *prev = head;
        // 確保當(dāng)前節(jié)點(diǎn)后還有節(jié)點(diǎn)
        while (prev->next != nullptr) {
            if (prev->next->val == val) {
                prev->next = prev->next->next;
            } else {
                prev = prev->next;
            }
        }
        return head;
    }
};

可以模擬下程序的執(zhí)行步驟，加深理解

四、總結(jié)

鏈表題涉及到指針的操作，應(yīng)當(dāng)足夠細(xì)心，栓新繩，解舊繩。
相似題型：反轉(zhuǎn)單鏈表

參考鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/203yi-chu-lian-biao-yuan-su-by-lewis-dxstabdzew/