C++實(shí)現(xiàn)LeetCode(203.移除鏈表元素)

第C++實(shí)現(xiàn)LeetCode(203.移除鏈表元素)[LeetCode]203.RemoveLinkedListElements移除鏈表元素

Removeallelementsfromalinkedlistofintegersthathavevalueval.

Example

Given:1--2--6--3--4--5--6,val=6

Return:1--2--3--4--5

Credits:

Specialthanksto@mithmattforaddingthisproblemandcreatingalltestcases.

這道移除鏈表元素是鏈表的基本操作之一，沒有太大的難度，就是考察了基本的鏈表遍歷和設(shè)置指針的知識(shí)點(diǎn)，我們只需定義幾個(gè)輔助指針，然后遍歷原鏈表，遇到與給定值相同的元素，將該元素的前后連個(gè)節(jié)點(diǎn)連接起來，然后刪除該元素即可，要注意的是還是需要在鏈表開頭加上一個(gè)dummynode，具體實(shí)現(xiàn)參見代碼如下：

解法一：

classSolution{

public:

ListNode*removeElements(ListNode*head,intval){

ListNode*dummy=newListNode(-1),*pre=dummy;

dummy-next=head;

while(pre-next){

if(pre-next-val==val){

ListNode*t=pre-next;

pre-next=t-next;

t-next=NULL;

deletet;

}else{

pre=pre-next;

returndummy-next;

};

如果只是為了通過OJ，不用寫的那么嚴(yán)格的話，下面這種方法更加簡潔，當(dāng)判斷下一個(gè)結(jié)點(diǎn)的值跟給定值相同的話，直接跳過下一個(gè)結(jié)點(diǎn)，將next指向下下一個(gè)結(jié)點(diǎn)，而根本不斷開下一個(gè)結(jié)點(diǎn)的next，更不用刪除下一個(gè)結(jié)點(diǎn)了。最后還要驗(yàn)證頭結(jié)點(diǎn)是否需要?jiǎng)h除，要的話直接返回下一個(gè)結(jié)點(diǎn)，參見代碼如下：

解法二：

classSolution{

public:

ListNode*removeElements(ListNode*head,intval){

if(!head)returnNULL;

ListNode*cur=head;

while(cur-next){

if(cur-next-val==val)cur-next=cur-next-next;

elsecur=cur-next;

returnhead-val==valhead-next:head;

};

我們也可以用遞歸來解，寫法很簡潔，通過遞歸調(diào)用到鏈表末尾，然后回來，需要要?jiǎng)h的元素，將鏈表next指針指向下一個(gè)元素即可：

解法三：

classSolution{

public:

ListNode*removeElements(ListNode*head,intval){

if(!head)returnNULL;

head-next=removeElements(head-next,val);

returnhead-val==valhead-next:head;

};

類似題目：

RemoveElement

DeleteNodeinaLinkedList

參考資料：

/problems/remove-linked-list-elements/

/problems/remove-linked-list-elements/discuss/57324/AC-Java-solution

/problems/remove-linked-list-elements/discuss/57306/3-line-recursive-sol