題目描述

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

解題思路

創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)dummyHead，并將其next指向給定的頭節(jié)點(diǎn)head，這樣可以避免處理頭節(jié)點(diǎn)的特殊情況。使用指針cur來(lái)遍歷鏈表，當(dāng)cur的下一個(gè)節(jié)點(diǎn)不為空時(shí)，進(jìn)行如下操作：
? 1.如果cur的下一個(gè)節(jié)點(diǎn)的值等于給定的數(shù)值val，則將其下一個(gè)節(jié)點(diǎn)（即要移除的節(jié)點(diǎn)）保存在臨時(shí)指針tmp中，然后將cur的next指針指向下下個(gè)節(jié)點(diǎn)，同時(shí)刪除tmp指向的節(jié)點(diǎn)，完成移除操作。
? 2.如果cur的下一個(gè)節(jié)點(diǎn)的值不等于給定的數(shù)值val，則將cur指針指向下一個(gè)節(jié)點(diǎn)，即保持鏈表的連續(xù)性。
? 3.最后，將head指向dummyHead的下一個(gè)節(jié)點(diǎn)，即新的頭節(jié)點(diǎn)，然后刪除dummyHead節(jié)點(diǎn)釋放內(nèi)存，最終返回新的頭節(jié)點(diǎn)。

算法實(shí)現(xiàn)

C++實(shí)現(xiàn)

/*** 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*dummyHead=new ListNode(0);dummyHead->next=head;ListNode*cur=dummyHead;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=dummyHead->next;delete dummyHead;return head;}
};

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中n是鏈表的長(zhǎng)度。需要遍歷整個(gè)鏈表一次。
• 空間復(fù)雜度：O(1)，只使用了常數(shù)級(jí)別的額外空間。

總結(jié)

=這種方法的時(shí)間復(fù)雜度和空間復(fù)雜度都很低，適用于處理大規(guī)模的鏈表數(shù)據(jù)。希望本篇博客能給大家提供一些幫助，也歡迎大家多多交流，共同進(jìn)步！

以上就是對(duì)LeetCode203移除鏈表元素的解題思路、算法實(shí)現(xiàn)、復(fù)雜度分析和總結(jié)，希望對(duì)你有所幫助！