C++實(shí)現(xiàn)LeetCode(203.移除鏈表元素)
[LeetCode] 203.Remove Linked List Elements 移除鏈表元素
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
這道移除鏈表元素是鏈表的基本操作之一，沒有太大的難度，就是考察了基本的鏈表遍歷和設(shè)置指針的知識點(diǎn)，我們只需定義幾個輔助指針，然后遍歷原鏈表，遇到與給定值相同的元素，將該元素的前后連個節(jié)點(diǎn)連接起來，然后刪除該元素即可，要注意的是還是需要在鏈表開頭加上一個dummy node，具體實(shí)現(xiàn)參見代碼如下：
解法一：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummy = new ListNode(-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;
delete t;
} else {
pre = pre->next;
}
}
return dummy->next;
}
};
如果只是為了通過OJ，不用寫的那么嚴(yán)格的話，下面這種方法更加簡潔，當(dāng)判斷下一個結(jié)點(diǎn)的值跟給定值相同的話，直接跳過下一個結(jié)點(diǎn)，將next指向下下一個結(jié)點(diǎn)，而根本不斷開下一個結(jié)點(diǎn)的next，更不用刪除下一個結(jié)點(diǎn)了。最后還要驗(yàn)證頭結(jié)點(diǎn)是否需要刪除，要的話直接返回下一個結(jié)點(diǎn)，參見代碼如下：
解法二：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return NULL;
ListNode *cur = head;
while (cur->next) {
if (cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return head->val == val ? head->next : head;
}
};
我們也可以用遞歸來解，寫法很簡潔，通過遞歸調(diào)用到鏈表末尾，然后回來，需要要刪的元素，將鏈表next指針指向下一個元素即可：
解法三：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return NULL;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};
類似題目：
參考資料：
https://leetcode.com/problems/remove-linked-list-elements/
https://leetcode.com/problems/remove-linked-list-elements/discuss/57324/AC-Java-solution
https://leetcode.com/problems/remove-linked-list-elements/discuss/57306/3-line-recursive-solution
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(203.移除鏈表元素)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)移除鏈表元素內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言的最大特點(diǎn)是：功能強(qiáng)、使用方便靈活。C編譯的程序?qū)φZ法檢查并不象其它高級語言那么嚴(yán)格，這就給編程人員留下“靈活的余地”，但還是由于這個靈活給程序的調(diào)試帶來了許多不便，尤其對初學(xué)C語言的人來說，經(jīng)常會出一些連自己都不知道錯在哪里的錯誤2013-07-07
這篇文章主要為大家詳細(xì)介紹了MFC實(shí)現(xiàn)漂亮界面之美化按鈕，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-02-02
C++ 11允許開發(fā)者們以標(biāo)準(zhǔn)的、不依賴于平臺的方式編寫多線程程序。這篇文章概述了標(biāo)準(zhǔn)庫對于線程和同步操作機(jī)制的支持。這些都是非常重要的知識，希望讀者們可以認(rèn)真看一下2021-06-06
詳解VS2019使用scanf()函數(shù)報錯的解決方法
本文主要介紹了詳解VS2019使用scanf()函數(shù)報錯的解決方法，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
雙鏈表：在單鏈表的每個結(jié)點(diǎn)中，再設(shè)置一個指向其前驅(qū)結(jié)點(diǎn)的指針域，下面這篇文章主要給大家介紹了關(guān)于利用C++實(shí)現(xiàn)雙鏈表基本接口的相關(guān)資料，需要的朋友可以參考借鑒，下面來一起看看吧。2017-08-08
Windows平臺下配置VS Code的C++環(huán)境教程
這篇文章主要介紹了Windows平臺下配置VS Code的C++環(huán)境教程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要介紹了淺析C++中的函數(shù)重載,在C++中，可以為兩個或兩個以上的函數(shù)提供相同的函數(shù)名稱，只要參數(shù)類型不同，或者參數(shù)類型相同而參數(shù)個數(shù)不同，又或者參數(shù)類型參數(shù)個數(shù)相同，參數(shù)次序不同，稱為函數(shù)重載,需要的朋友可以參考下2023-08-08
今天小編就為大家分享一篇關(guān)于C++生成和解析XML文件的講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C語言實(shí)現(xiàn)掃雷游戲小項(xiàng)目
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)掃雷游戲小項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
詳解C語言中雙向循環(huán)鏈表的實(shí)現(xiàn)
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。本文將用C語言實(shí)現(xiàn)雙向循環(huán)鏈表，需要的可以參考一下2022-06-06