目錄

題目描述：

題目解讀（分析）

解決代碼

---

題目描述：

給你一個鏈表的頭節點?head?和一個整數?val?，請你刪除鏈表中所有滿足?Node.val == val?的節點，并返回?新的頭節點?。

題目解讀（分析）:

對于需要刪除鏈表中val的值，我們立馬可以想到一種方法一就是遍歷循環尋找val這個值，進行刪除該節點，這中方法是最容易想出來的，可是時間復雜度是為O()。

而這里我們還有一種方法二就是用類似空間換時間的方法（這里沒有向內存申請空間，也同樣將時間復雜度降為O(n)）。這里我們著重講解這個方法，這個方法就是直接創建一個新的鏈表來收集刪除所有刪除val值的節點，并進行連接。如圖展示：

寫代碼過程中我們需要使用ptail來遍歷新鏈表，plist來存儲新鏈表的頭節點，而pcur是用來遍歷原鏈表和val進行比較，然后得到符合題意的節點移動到ptail中。在最后時如果ptail不為空，那就必須將ptail->next置空，可以將這個作為結束節點，避免返回不符合題意值。

解決代碼:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
ListNode* removeElements(ListNode* head, int val) {//  assert(head);ListNode* plist = NULL;//存儲ListNode* ptail = NULL;//篩選ListNode* pcur = head;//遍歷while (pcur){if(pcur->val != val){if(ptail == NULL){ptail = plist = pcur;}else{ptail->next = pcur;ptail = ptail->next;}}pcur=pcur->next;}//考慮為空if(plist != NULL){ptail->next = NULL;}return plist;
}