?？途W(wǎng)高頻算法題系列-BM16-刪除有序鏈表中重復(fù)的元素-II

題目描述

給出一個升序排序的鏈表，刪除鏈表中的所有重復(fù)出現(xiàn)的元素，只保留原鏈表中只出現(xiàn)一次的元素。

原題目見：BM16 刪除有序鏈表中重復(fù)的元素-II

解法一：鏈表遍歷

首先，考慮特殊情況，如果鏈表為空或者只有一個結(jié)點，不會有重復(fù)的元素，返回原鏈表。

否則，遍歷鏈表判斷是否有重復(fù)元素，處理過程如下：

• 首先，因為頭結(jié)點也可能重復(fù)，所以使用一個虛擬頭結(jié)點dummyNode；

• 然后，用lastNonRedundantNode為上一個不重復(fù)的結(jié)點，初始化為頭結(jié)點，count記錄該結(jié)點的元素的重復(fù)次數(shù)，初始為1；

• 然后從原鏈表的第二個結(jié)點開始遍歷；

• 如果當(dāng)前結(jié)點的值和lastNonRedundantNode不相同，判斷l(xiāng)astNonRedundantNode出現(xiàn)的次數(shù)，如果只出現(xiàn)過一次，則是一個不重復(fù)的結(jié)點，更新pre；否則不更新pre。更新lastNonRedundantNode，并將count重置為1。

• 如果當(dāng)前結(jié)點的值和lastNonRedundantNode相同，則將count加1。

• 最后，判斷最后一個結(jié)點出現(xiàn)的次數(shù)，如果count為1，則也是不重復(fù)的結(jié)點。

最后，返回新構(gòu)造的不重復(fù)元素的鏈表。

代碼

$1.01^\approx 37.7834343329$ ?
$0.99^\approx 0.02551796445$ ?
相信堅持的力量！ ?