您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“C++怎么移除有序鏈表中的重復(fù)項(xiàng)”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“C++怎么移除有序鏈表中的重復(fù)項(xiàng)”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來(lái)學(xué)習(xí)新知識(shí)吧。
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
這道題讓我們移除給定有序鏈表的重復(fù)項(xiàng),那么可以遍歷這個(gè)鏈表,每個(gè)結(jié)點(diǎn)和其后面的結(jié)點(diǎn)比較,如果結(jié)點(diǎn)值相同了,只要將前面結(jié)點(diǎn)的 next 指針跳過(guò)緊挨著的相同值的結(jié)點(diǎn),指向后面一個(gè)結(jié)點(diǎn)。這樣遍歷下來(lái),所有重復(fù)的結(jié)點(diǎn)都會(huì)被跳過(guò),留下的鏈表就是沒(méi)有重復(fù)項(xiàng)的了,代碼如下:
解法一:
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode *cur = head; while (cur && cur->next) { if (cur->val == cur->next->val) { cur->next = cur->next->next; } else { cur = cur->next; } } return head; } };
我們也可以使用遞歸的方法來(lái)做,首先判斷是否至少有兩個(gè)結(jié)點(diǎn),若不是的話,直接返回 head。否則對(duì) head->next 調(diào)用遞歸函數(shù),并賦值給 head->next。這里可能比較暈,先看后面一句,返回的時(shí)候,head 結(jié)點(diǎn)先跟其身后的結(jié)點(diǎn)進(jìn)行比較,如果值相同,那么返回后面的一個(gè)結(jié)點(diǎn),當(dāng)前的 head 結(jié)點(diǎn)就被跳過(guò)了,而如果不同的話,還是返回 head 結(jié)點(diǎn)??梢园l(fā)現(xiàn)了,進(jìn)行實(shí)質(zhì)上的刪除操作是在最后一句進(jìn)行了,再來(lái)看第二句,對(duì) head 后面的結(jié)點(diǎn)調(diào)用遞歸函數(shù),那么就應(yīng)該 suppose 返回來(lái)的鏈表就已經(jīng)沒(méi)有重復(fù)項(xiàng)了,此時(shí)接到 head 結(jié)點(diǎn)后面,在第三句的時(shí)候再來(lái)檢查一下 head 是否又 duplicate 了,實(shí)際上遞歸一直走到了末尾結(jié)點(diǎn),再不斷的回溯回來(lái),進(jìn)行刪除重復(fù)結(jié)點(diǎn),參見(jiàn)代碼如下:
解法二:
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (!head || !head->next) return head; head->next = deleteDuplicates(head->next); return (head->val == head->next->val) ? head->next : head; } };
讀到這里,這篇“C++怎么移除有序鏈表中的重復(fù)項(xiàng)”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。