1.2 如何從無序鏈表中移除重復項

【出自GG面試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

給定一個沒有排序的鏈表，去掉其重復項，并保留原順序，如鏈表1→3→1→5→5→7，去掉重復項后變為1→3→5→7。

分析與解答：

方法一：順序刪除

主要思路為：通過雙重循環直接在鏈表上執行刪除操作。外層循環用一個指針從第一個結點開始遍歷整個鏈表，然后內層循環用另外一個指針遍歷其余結點，將與外層循環遍歷到的指針所指結點的數據域相同的結點刪除，如下圖所示。

假設外層循環從outerCur開始遍歷，當內層循環指針innerCur遍歷到上圖實線所示的位置（outerCur.data==innerCur.data）時，此時需要把innerCur指向的結點刪除。具體步驟如下：

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

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

3）從鏈表中刪除tmp結點。

實現代碼如下：

程序的運行結果為

算法性能分析：

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

方法二：遞歸法

主要思路為：對于結點cur，首先遞歸地刪除以cur.next為首的子鏈表中重復的結點，接著從以cur.next為首的子鏈表中找出與cur有著相同數據域的結點并刪除。實現代碼如下：

算法性能分析：

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

方法三：空間換時間

通常情況下，為了降低時間復雜度，往往在條件允許的情況下，通過使用輔助空間實現。具體而言，主要思路如下。

1）建立一個HashSet，HashSet中的內容為已經遍歷過的結點內容，并將其初始化為空。

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

① 如果結點內容已經在HashSet中，則刪除此結點，繼續向后遍歷。

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

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

分析與解答：

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

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

2）如果cur.data!=cur.next.data，那么cur=cur.next，繼續遍歷其余結點。