1. 題目

描述

給出一個升序排序的鏈表，刪除鏈表中的所有重復出現的元素，只保留原鏈表中只出現一次的元素。 例如： 給出的鏈表為1→2→3→3→4→4→5, 返回1→2→5. 給出的鏈表為1→1→1→2→3 返回2→3.

數據范圍：鏈表長度 0≤n≤100000 ，鏈表中的值滿足 ∣val∣≤1000

要求：空間復雜度 O(n)，時間復雜度 O(n)

進階：空間復雜度 O(1)，時間復雜度 O(n)

示例1

輸入：

{1,2,2}

返回值：

{1}

示例2

輸入：

{}

返回值：

{}

2. 解題思路

本題要求刪除重復的元素即在鏈表中重復的元素都會被刪除，由于重復的元素也有可能是頭結點，因此需要定義一個鏈表的虛擬頭結點，虛擬頭結點的指針域指向鏈表的頭結點。

假如鏈表結構如下圖所示：

這時可以通過以下步驟完成鏈表重復元素的刪除。

步驟一：定義虛擬頭結點、指針變量。

cur ：鏈表節點銜接指針（當前操作的節點）；

nxt1：操作的下一個節點；

nxt2 ：操作的下下一個節點。

步驟二：循環刪除鏈表的重復節點。

此時，nxt1與nxt2對應的節點值都是1（重復的元素），移動nxt2。

此時，nxt1與nxt2對應的節點值還是1（重復的元素），移動nxt2。

這時，nxt1的節點值是1，nxt2的值是2，需將已經檢查出重復的元素1刪除。刪除重復元素1可以通過更改cur當前節點的指針域，讓它指向nxt2，這樣就可以將多個1節點刪除。

之后再移動nxt1與nxt2，使得nxt1始終指向當前操作節點cur的下一個節點；nxt2始終指向當前操作節點cur的下下一個節點。

ntx1 = cur.next # 下一個節點

ntx2 = cur.next.next # 下下一個節點

此時，nxt1與ntx2對應的節點值都是2（重復的元素），移動nxt2。

這時，nxt1的節點值是2，nxt2的值是3，需將已經檢查出重復的元素2刪除。刪除重復元素2可以通過更改cur當前節點的指針域，讓它指向nxt2，這樣就可以將多個2節點刪除。

之后再移動nxt1與nxt2，這時發現nxt1與nxt2中有一個為Null，循環退出（重復元素刪除完成）。

步驟三：返回鏈表中無重復節點組成的鏈表頭結點。

虛擬頭節點的下一個節點就是需要返回的鏈表頭節點，將其返回。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python版本：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1370403

• Java版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1366847

• Golang版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364604

3. 編碼實現

核心偽代碼如下：

函數 刪除重復節點(頭節點 head) 返回 鏈表節點:如果 head 為空:返回 head//1. 定義虛擬頭結點、指針變量創建虛擬頭節點 tmp_head，值為 -1tmp_head的下一個節點指向 head當前節點 cur 指向 tmp_head//2. 循環刪除鏈表的重復節點當 cur的下一個節點 不為空 且 cur的下一個節點的下一個節點 不為空 時，循環執行:ntx1 = cur的下一個節點ntx2 = cur的下一個節點的下一個節點如果 ntx1的值 == ntx2的值:val = ntx1的值當 ntx2 不為空 且 ntx2的值 == val 時，循環執行:ntx2 = ntx2的下一個節點cur的下一個節點 = ntx2  # 跳過所有重復節點否則:cur = cur的下一個節點  # 移動指針到下一個非重復節點// 3.返回鏈表中無重復節點組成的鏈表頭結點返回 tmp_head的下一個節點  # 返回處理后的鏈表頭節點

具體完整代碼你可以參考下面視頻的詳細講解。

• Python版本：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1370403

• Java版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1366847

• Golang版本：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364604

4.小結

本題要求刪除重復的元素即在鏈表中重復的元素都會被刪除，由于重復的元素也有可能是頭結點，因此需要定義一個鏈表的虛擬頭結點，虛擬頭結點的指針域指向鏈表的頭結點。

這時可以通過以下步驟完成鏈表重復元素的刪除。（1）定義虛擬頭結點、指針變量；（2）循環刪除鏈表的重復節點；（3）返回鏈表中無重復節點組成的鏈表頭結點。

《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：

? 鏈表 ? 二叉樹 ?二分查找、排序 ? 堆、棧、隊列 ?回溯算法 ? 哈希算法 ? 動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1509965

• Java編碼實現：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1510007

• Golang編碼實現：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1509945

對于鏈表的相關操作，我們總結了一套【可視化+圖解】方法，依據此方法來解決鏈表相關問題，鏈表操作變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：千淘萬漉雖辛苦，吹盡狂沙始到金。