Leetcode之旅|刪除鏈表中重複元素

02-12

圖片出處，侵刪

　　自從前兩天刷了那道鏈表的題之後覺得很有意思，奇妙的數據結構哇咔咔 ~ ~ ~ 但畢竟不是科班出身，對它的一些操作非常不熟悉，每次被各種head,tail,pre,next指來指去的東西繞得暈頭轉向。嗯，熟能生巧，所以我最近專註於刷鏈表相關的題目啊哈哈 ~ ~ ~

題目描述

　　這篇博客回顧的題目是刪除鏈表中重複元素的問題（鏈表均已排好序）：

　　基礎版：只刪除重複了的元素，即保證唯一性（Leetcode Problem 83 ）。

　　進階版：刪除有重複出現過的元素，即如果元素重複了，就將其從鏈表中剔除（Leetcode Problem 82 ）。

　　發現我的語言很蒼白，還是看實例吧：

　　基礎包：

Given 1->2->3->3->4->4->5, return 1->2->5.Given 1->1->1->2->3, return 2->3.

　　升級包：

Given 1->2->3->3->4->4->5, return 1->2->5.Given 1->1->1->2->3, return 2->3.

解題思路及相關代碼

基礎版

　　對於基礎包而言，我們只需要一個指針，即下面代碼中的cur，從head開始挨個遍歷鏈表節點（所以鏈表已經排序好這個前提很重要），對於每個cur，將其與其後繼的節點值比較，如果相同，說明這個後繼需要刪除，對鏈表而言，操作則相當簡單，直接將cur的後繼改為當前後繼的後繼即可。如果不同，說明沒有與當前節點值重複的了，直接將當前節點後移即可，即將cur更新為當前節點的後繼。

　　代碼如下：

def deleteDuplicates(head): """ :type head: ListNode :rtype: ListNode """ # 鏈表為空的特殊情況 if not head: return head # 當前節點初始化為表頭 cur = head # 遍歷，循環條件為當前節點和當前節點的後繼不為空 while cur and cur.next: # 如果當前節點值和其後繼值相等，則將其後繼改為後繼的後繼 if cur.val == cur.next.val: cur.next = cur.next.next # 如果不相等，則將當前節點更新 else: cur = cur.next return head

進階版

　　和基礎版相比，進階版的難度體現在兩個方面：第一，因為重複出現過的元素需要刪除，所以表頭可能會被修改（如第一次出現的元素就重複的情況）；第二，因為重複出現過的元素很隨機，所以一個指針不夠提供足夠的信息，比如上述例子中的第一個，在將3和4刪除後，得知道5的前驅是2。

　　對此，我的解決方案是：

　　１.　使用兩個指針，一個用來指代當前節點(cur)，初始化為表頭，另一個為前驅節點(pre)，可以在刪除重複節點後，給下一個節點提供前驅信息，初始化為Null。

　　2.　從當前節點開始遍歷鏈表，從簡單的情況開始處理，即如果當前值不等於其後繼值，那麼非常lucky，這個節點不重複了，將前驅節點更新為當前節點，將當前節點更新為其後繼節點，然後跳出本次循環，move on；

　　3.　如果相等呢？那我們就得順著往下捋,即更新後繼節點next，直到不相等了，這時next指向的是第一個不與前面節點重複的節點，而cur指向的是這批重複節點的第一個節點。那麼這時要刪除的話就有兩種情況了:第一，如果重複段在表頭，說明head要更新，更新為next節點了，這時pre依舊指向Null，然後將cur更新為next；第二，如果這批重複的是中間的批次，說明head不用更新了，但因為中間這批重複的全刪了，所以pre的後繼得更新為next，和第一種情況一樣，cur也要後移，即更新為next。

　　代碼如下：

def deleteDuplicates(head): """ :type head: ListNode :rtype: ListNode """ if not head: return head # 兩個指針：pre和cur pre = None cur = head # 遍歷所有節點 while cur: # 一個臨時指針指向cur的後繼 _next = cur.next if not _next: return head # 如果兩個值不相等，則將pre和cur都往後移 elif cur.val != _next.val: pre = cur cur = _next continue # 如果相等，則將_next一直捋到不重複為止 else: while _next and _next.val == cur.val: _next = _next.next # 如果重複段在表頭，則需要更新表頭信息 if cur == head: head = _next # 如果重複段在中間，則需要將pre的後繼更新為_next else: pre.next = _next # 繼續遍歷 cur = _next return head

結果

　　測試：均已通過

思考：

　　１.　基礎版是用迭代法，「凡是迭代即可遞歸」，試試遞歸如何實現？

　　2.　進階版是最優化的嗎？可以逛逛discuss看是否還可進一步優化？

我是個人博客搬運工~~~

Leetcode之旅|鏈表啊，鏈表！(1)www.quanlion.com