如果您是第一次看我寫(xiě)的博客，可以給我點(diǎn)個(gè)贊并關(guān)注我嗎，我會(huì)持續(xù)分享更多有意思的干貨。

文章目錄

• • 1 題目
  • 2 思路
  • 3 代碼
  • 4 小結(jié)

1 題目

Leetcode203 移除鏈表元素

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val ，請(qǐng)你刪除鏈表中所有滿足 Node.val == val 的節(jié)點(diǎn)，并返回 新的頭節(jié)點(diǎn) 。

示例 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é)點(diǎn)數(shù)目在范圍 [0, 104] 內(nèi)
• 1 <= Node.val <= 50
• 0 <= val <= 50

2 思路

一開(kāi)始做這道題，我是直接上來(lái)就做的，但是出現(xiàn)一個(gè)問(wèn)題，原文是不帶頭結(jié)點(diǎn)的單鏈表，這就導(dǎo)致可能出現(xiàn)兩種情況：一種是鏈表中每個(gè)元素都刪除，刪到后面什么都沒(méi)有了，頭指針指向NULL，且鏈表中如果只剩下一個(gè)結(jié)點(diǎn)我們是要做if判斷，因?yàn)閯h除鏈表中的最后一個(gè)結(jié)點(diǎn)是一種特殊情況。

還有一種情況是，如果是鏈表本身什么都沒(méi)有，這種情況也很難受。

對(duì)此，我們可以采用補(bǔ)頭結(jié)點(diǎn)的方式。也就是說(shuō)，我們可以指定一個(gè)虛擬頭結(jié)點(diǎn)，然后補(bǔ)在原始鏈表的最前面，這樣上面兩種情況都可以避免。（為什么？）

避免的原因是，如果鏈表中不帶頭結(jié)點(diǎn)的情況下刪除最后一個(gè)結(jié)點(diǎn)，是要做特殊情況處理，而帶頭結(jié)點(diǎn)的話，就不需要，因?yàn)閯h除一個(gè)結(jié)點(diǎn)通常是采用一個(gè)前置指針加上一個(gè)刪除結(jié)點(diǎn)指針進(jìn)行操作，而前置指針可以處在虛擬頭結(jié)點(diǎn)上。

如果是鏈表本身什么都沒(méi)有，那循環(huán)就不必開(kāi)始。

做完這些之后，根據(jù)題意要求，我們要返回新的頭結(jié)點(diǎn)。對(duì)于題意來(lái)說(shuō)，它要的單鏈表是不帶頭結(jié)點(diǎn)的，所以當(dāng)我們補(bǔ)上一個(gè)虛擬頭結(jié)點(diǎn)后，我們要返回的自然是虛擬頭結(jié)點(diǎn)的后面一個(gè)結(jié)點(diǎn)的指針。

好了，說(shuō)了這么多，開(kāi)始寫(xiě)代碼了！

3 代碼

/*** 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) {//建立虛擬頭結(jié)點(diǎn)ListNode *dummyHead = new ListNode;//將虛擬頭結(jié)點(diǎn)接入鏈表dummyHead->val = 0;dummyHead->next = head;ListNode * pre = dummyHead;while(pre->next != NULL){if(pre->next->val == val){ListNode * temp = dummyHead;temp = pre->next;pre->next = temp->next;delete(temp);}elsepre = pre->next;}return dummyHead->next;} };

4 小結(jié)

• 時(shí)間復(fù)雜度：O(n)，其中 n是鏈表的長(zhǎng)度。需要遍歷鏈表一次。
• 空間復(fù)雜度：O(1)。

這道題的巧妙之處在于添加頭結(jié)點(diǎn)來(lái)避免過(guò)多地判斷特殊情況，由此在其他的題目中，我們也可以遷移地去學(xué)習(xí)。當(dāng)然本題求解采用的是迭代的方式，如果喜歡用遞歸的同學(xué)也可以采用遞歸來(lái)處理這道題。

總結(jié)

以上是生活随笔為你收集整理的每日一题——Leetcode203 移除链表元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。