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

為天水等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及天水網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計、做網(wǎng)站、天水網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

順序刪除

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

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

具體步驟如下：

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

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

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

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

運行結(jié)果：

算法性能分析

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

遞歸法

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

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

算法性能分析

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

空間換時間

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

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

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

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

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

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

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

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

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

分析與解答

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

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

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

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

文章題目：怎么從無序鏈表中移除重復(fù)項
本文路徑：http://chinadenli.net/article24/gijsce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、用戶體驗、品牌網(wǎng)站建設(shè)、建站公司、自適應(yīng)網(wǎng)站、手機網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)