怎么從無序鏈表中移除重復項

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

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

順序刪除

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

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

具體步驟如下：

• 用tmp記錄待刪除的結點的地址。

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

• 從鏈表中刪除tmp結點。

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

運行結果：

算法性能分析

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

遞歸法

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

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

算法性能分析

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

空間換時間

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

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

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

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

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

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

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

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

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

分析與解答

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

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

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

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

文章題目：怎么從無序鏈表中移除重復項
本文路徑：http://bm7419.com/article24/gijsce.html

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

廣告

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