怎么從無(wú)序鏈表中移除重復(fù)項(xiàng)

本篇內(nèi)容主要講解“怎么從無(wú)序鏈表中移除重復(fù)項(xiàng)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“怎么從無(wú)序鏈表中移除重復(fù)項(xiàng)”吧!

順序刪除

通過(guò)雙重循環(huán)直接在鏈表上執(zhí)行刪除操作。外層循環(huán)用一個(gè)指針從第一個(gè)結(jié)點(diǎn)開(kāi)始遍歷整個(gè)鏈表，然后內(nèi)層循環(huán)用另外一個(gè)指針遍歷其余結(jié)點(diǎn)，將與外層循環(huán)遍歷到的指針?biāo)附Y(jié)點(diǎn)的數(shù)據(jù)域相同的結(jié)點(diǎn)刪除，如下圖所示。

假設(shè)外層循環(huán)從outerCur開(kāi)始遍歷，當(dāng)內(nèi)層循環(huán)指針innerCur遍歷到上圖實(shí)線所示的位置(outerCur.data==innerCur.data)時(shí)，此時(shí)需要把innerCur指向的結(jié)點(diǎn)刪除。

具體步驟如下：

• 用tmp記錄待刪除的結(jié)點(diǎn)的地址。

• 為了能夠在刪除tmp結(jié)點(diǎn)后繼續(xù)遍歷鏈表中其余的結(jié)點(diǎn)，使innerCur指針指向它的后繼結(jié)點(diǎn)：innerCur=innerCur.next。

• 從鏈表中刪除tmp結(jié)點(diǎn)。

實(shí)現(xiàn)代碼如下：

運(yùn)行結(jié)果：

算法性能分析

由于這種方法采用雙重循環(huán)對(duì)鏈表進(jìn)行遍歷，因此，時(shí)間復(fù)雜度為O(N^2)。其中，N為鏈表的長(zhǎng)度。在遍歷鏈表的過(guò)程中，使用了常量個(gè)額外的指針變量來(lái)保存當(dāng)前遍歷的結(jié)點(diǎn)、前驅(qū)結(jié)點(diǎn)和被刪除的結(jié)點(diǎn)，因此，空間復(fù)雜度為O(1)。

遞歸法

主要思路為：對(duì)于結(jié)點(diǎn)cur，首先遞歸地刪除以cur.next為首的子鏈表中重復(fù)的結(jié)點(diǎn)，接著從以cur.next為首的子鏈表中找出與cur有著相同數(shù)據(jù)域的結(jié)點(diǎn)并刪除。

實(shí)現(xiàn)代碼如下：

算法性能分析

這種方法與方法一類似，從本質(zhì)上而言，由于這種方法需要對(duì)鏈表進(jìn)行雙重遍歷，因此，時(shí)間復(fù)雜度為O(N^2)。其中，N為鏈表的長(zhǎng)度。由于遞歸法會(huì)增加許多額外的函數(shù)調(diào)用，因此，從理論上講，該方法效率比前面的方法低。

空間換時(shí)間

通常情況下，為了降低時(shí)間復(fù)雜度，往往在條件允許的情況下，通過(guò)使用輔助空間實(shí)現(xiàn)。

具體而言，主要思路如下。

• 建立一個(gè)HashSet，HashSet中的內(nèi)容為已經(jīng)遍歷過(guò)的結(jié)點(diǎn)內(nèi)容，并將其初始化為空。

• 從頭開(kāi)始遍歷鏈表中的所以結(jié)點(diǎn)，存在以下兩種可能性：

• 如果結(jié)點(diǎn)內(nèi)容已經(jīng)在HashSet中，則刪除此結(jié)點(diǎn)，繼續(xù)向后遍歷。

• 如果結(jié)點(diǎn)內(nèi)容不在HashSet中，則保留此結(jié)點(diǎn)，將此結(jié)點(diǎn)內(nèi)容添加到HashSet中，繼續(xù)向后遍歷。

「引申：如何從有序鏈表中移除重復(fù)項(xiàng)?」

如鏈表：1,3、5、5、7、7、8、9

去重后：1,3、5、7、8、9

分析與解答

上述介紹的方法也適用于鏈表有序的情況，但是由于以上方法沒(méi)有充分利用到鏈表有序這個(gè)條件，因此，算法的性能肯定不是最優(yōu)的。本題中，由于鏈表具有有序性，因此，不需要對(duì)鏈表進(jìn)行兩次遍歷。所以，有如下思路：用cur  指向鏈表第一個(gè)結(jié)點(diǎn)，此時(shí)需要分為以下兩種情況討論。

• 如果cur.data==cur.next.data，那么刪除cur.next結(jié)點(diǎn)。

• 如果cur.data!=cur.next.data，那么cur=cur.next，繼續(xù)遍歷其余結(jié)點(diǎn)。

到此，相信大家對(duì)“怎么從無(wú)序鏈表中移除重復(fù)項(xiàng)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！