https://leetcode.cn/problems/remove-linked-list-elements/description/
一、題目分析
????????給你一個鏈表的頭節點?head?和一個整數?val?，請你刪除鏈表中所有滿足?Node.val == val?的節點，并返回?新的頭節點?。
? ? ? ? 今天的題目非常好理解，也就是要刪除掉鏈表中==val的值，并返回新的頭節點。
二、相關知識了解
? ? ? ? 鏈表這種數據結構其實與數組相似，同屬線性表，但是與數組相比的話，鏈表是不支持隨機訪問元素的，也就是說要想在鏈表中查詢一個元素的位置的話，時間復雜度最壞為O(n)（如果要查找的元素位于鏈表末尾（或不存在），需要遍歷整個鏈表，遍歷次數為n次。）。平均也就是O(（n + 1）/ 2)（這里就不過多的推導了，感興趣的同學可以期待一下下一期的題目，我會詳細帶著大家一起設計出一個功能相對完善的鏈表）
對比數組的隨機訪問
-
數組支持隨機訪問（通過下標），查詢時間為?O(1)，這是鏈表與數組的核心差異之一。
-
但鏈表在插入/刪除節點（尤其頭部）時更高效 O(1)，而數組可能需要移動元素（O(n)）。
三、示例分析
輸入：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 輸出：[]
四、解題思路&代碼實現
? ? ? ? 方法一：原鏈表刪除元素（復雜度為O(n)）
? ? ? ? ? ?首先，拿到一個鏈表第一步我們要進行的是判斷該鏈表是否為空，如果為空的話直接return head就好。其次就是判斷當前節點的值是否==val。如果==的話那么就需要對該節點進行刪除操作。下面看一下具體代碼的實現。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 處理頭節點等于val的情況（可能需要連續刪除多個頭節點 如示例3）while (head && head->val == val) {ListNode* temp = head; // 臨時保存當前頭節點head = head->next; // 頭節點指向下一個節點delete temp; // 釋放原頭節點的內存}// 遍歷鏈表，刪除非頭節點中值等于val的節點ListNode* cur = head; // 當前節點指針while (cur && cur->next) { // 當前節點和下一個節點均非空時循環if (cur->next->val == val) {// 如果下一個節點值等于val，則刪除它ListNode* temp = cur->next; // 臨時保存待刪除節點cur->next = cur->next->next; // 跳過待刪除節點，直接連接下下個節點delete temp; // 釋放待刪除節點的內存} else {// 否則，移動到下一個節點繼續檢查cur = cur->next;}}return head; // 返回處理后的鏈表頭節點}
};? ? ? ? 這里需要注意幾個關鍵點：
- 首先在C/C++中堆區開辟的空間需進行手動釋放，以免造成空間浪費，或者該空間內的臟數據影響程序結果。（一定要養成良好的編程習慣）
- 在第二個while語句終止條件中，一定要cur和cur->next都不為空時我們再去進行循環體，確保不會訪問到空指針。最終返回的head節點有可能為NULL，也就是示例3的情況。
- 在進行頭節點的處理使用while處理連續多個頭節點值等于?
val?的情況而不是if（if只能處理一次）（例如?[1,1,1,2]?刪除?1）。每次刪除節點時記得更新head節點，并使用delete釋放內存 -
如果?
cur->next?的值等于?val，則修改?cur->next?跳過該節點，并釋放內存。如果不等，則正常移動到下一個節點。
????????方法二：虛擬頭節點法（復雜度為O(n)）
? ? ? ? ? 虛擬頭節點法屬于是對法一進行的一個優化操作，可以顯著簡化鏈表操作，尤其是在處理涉及頭節點刪除或修改的問題時。
? ? ? ? 對比法一的優點：
- 無需特殊處理頭節點，虛擬頭節點始終作為鏈表的“前置節點”，使得真正的頭節點（
dummy->next）和其他節點的刪除邏輯完全一致，避免分支判斷。 - 簡化代碼的結構，法一需要進行兩步操作，需先對頭節點進行預處理操作，再去處理其余節點。而使用虛擬頭節點則只需要一個循環即可處理所有節點，避免代碼冗余從而簡化代碼。
-
虛擬頭節點確保?
cur?初始指向一個非空節點（dummy），因此?cur->next?的訪問總是安全的（無需額外判空）。
? ? ? ? 具體實現代碼如下：
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 創建虛擬頭節點(dummy node)，其值任意（這里設為0），next指向原鏈表頭節點// 使用虛擬頭節點可以統一處理原頭節點和其他節點的刪除邏輯ListNode* dummy = new ListNode(0);dummy->next = head; // 將虛擬頭節點連接到原鏈表// cur指針用于遍歷鏈表，初始指向虛擬頭節點ListNode* cur = dummy;// 遍歷鏈表，檢查每個節點的下一個節點（cur->next）while (cur->next) {if (cur->next->val == val) { // 如果下一個節點的值等于目標值ListNode* temp = cur->next; // 臨時保存要刪除的節點cur->next = cur->next->next; // 跳過要刪除的節點，直接連接下下個節點delete temp; // 釋放要刪除節點的內存（避免內存泄漏）// 注意：這里不移動cur指針，因為新的cur->next可能也需要刪除// 例如鏈表[1,2,2,3]，刪除2時需要連續檢查} else {cur = cur->next; // 如果不需要刪除，則正常移動到下一個節點}}// 返回處理后的鏈表頭節點（即dummy->next）// 注意：原頭節點可能已被刪除，dummy->next會自動更新為新的頭節點ListNode* newHead = dummy->next;delete dummy; // 釋放虛擬頭節點的內存return newHead;}
};????????關鍵點說明：
- 虛擬頭節點：創建一個虛擬頭節點作為原鏈表的起始點，其next指針指向的為原鏈表的head節點?（作用：統一處理邏輯，避免單獨進行頭節點刪除操作）
- 返回值：這里需要注意我們需要返回的值應為虛擬頭節點的next，若原鏈表所有節點都已被刪除，那么虛擬頭節點的next會變為NULL，則無需處理。
????????其余與方法一相同！
至此算法已經是最優解！完結撒花！！！🌸🌸🌸
四、題目總結? ? ?
方法一：原鏈表刪除元素
此方法先對頭節點進行處理，若頭節點的值等于?val，則連續刪除頭節點直至其值不等于?val。之后遍歷鏈表，對非頭節點中值等于?val?的節點進行刪除操作。該方法時間復雜度為?O(n)，不過在處理頭節點時需要額外的邏輯判斷，且要分別處理頭節點和非頭節點的刪除情況，代碼相對復雜。
方法二：虛擬頭節點法
這種方法創建了一個虛擬頭節點，將其?next?指針指向原鏈表的頭節點。通過遍歷鏈表，檢查每個節點的下一個節點，若其值等于?val?則進行刪除。此方法的優點在于統一了頭節點和其他節點的刪除邏輯，避免了額外的分支判斷，簡化了代碼結構。時間復雜度同樣為?O(n)，是對方法一的優化。
總結
在處理鏈表刪除操作時，使用虛擬頭節點能有效簡化代碼，避免因頭節點的特殊情況而增加的復雜邏輯，提高代碼的可讀性和可維護性。兩種方法的時間復雜度均為線性，已達到最優解。在實際編程中，要養成手動釋放堆區內存的習慣，防止內存泄漏。今天的題解分享到這里，謝謝大家！！！荊軻刺秦！！！
