本文始發於個人公衆號： TechFlow ，原創不易，求個關注

今天是 LeetCode專題 的第51篇文章，我們來看LeetCode第82題，刪除有序鏈表中的重複元素II(Remove Duplicates from Sorted List II)。

這題官方給出的難度是 Medium ，點贊1636，反對107，通過率在36.3%左右。根據我們之前的分析，這題的難度適中，並且質量很高，好評如潮。實際上也的確如此，這題算法本身並不難，但是想要完整沒有bug地實現並不容易，我們一起來看看。

題意

給定一個有序的 存在重複元素的鏈表 ，要求移除掉鏈表當中所有的重複元素。返回一個不包含重複元素的鏈表。

這裏要注意的一點，這題讓我們做的事情並不是去重，就是去除掉多餘的元素，而是要去除掉所有重複的元素。比如2在鏈表當中出現了兩次，屬於重複元素，我們要做的並不是去掉一個2，僅保留一個，而是要 將所有的2都去除 ，因爲2屬於重複元素。

我們來看樣例：

Input: 1->2->3->3->4->4->5
Output: 1->2->5

原鏈表當中的3和4都屬於重複元素，所以被去除了。

Input: 1->1->1->2->3
Output: 2->3

解法

前面說了這題的質量很高，這題是屬於典型的解法赤裸裸，但是很多人就是寫不出來的題， 非常考察基本功 。適合用在校招面試當中，如果我有幸去面試校招生， 我可能會選這道題。不存在算法會不會的問題，寫不出來一定是基本功不夠紮實。

鏈表已經有序了，那麼 相同的元素必然會排在一起 ，我們只需要將它們移除就可以了。但是說起來簡單，要在鏈表當中實現並不容易。難點主要有兩個，一個是鏈表增刪節點的操作很多人不熟悉，尤其是像是C++這樣的語言涉及指針，可能更不容易。另外一個難點就在題意當中，我們要做的不是去重，而是 要所有重複的元素全部刪除 。

看起來似乎和去重沒什麼差別， 如果你真這麼想，並且着手去實現，那麼幾乎可以肯定一定會遇到問題。

因爲鏈表是單向的，假設你當前的指針是cur，當你發現cur這個指針的元素存在重複的時候，你需要連當前這個節點一起刪除。我們都知道， 單向鏈表是不能走回頭路的，而刪除節點，必須要用到前一個節點的指針 。再加上判斷元素重複需要用到的指針，會需要我們同時維護多個指針，增加代碼的編碼難度。

針對這個問題，我們有兩種解決思路。第一種是我們不在原鏈表上處理，而是 創建一個新的鏈表進行返回 。所以我們要做的就不是刪除元素，而是插入元素，只有發現當前元素不存在重複的時候纔會插入鏈表。最後返回的也是一個全新的鏈表。

這當然是可以的，也是沒有問題了，我第一次做這道題就是採取的這種措施。相比之下， 這種方法會容易一些，因爲我們 不需要判斷太多的指針和位置 ，我貼一下當時的代碼： 

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
          // 如果元素少於2個則直接返回
        if (head == nullptr || head->next == nullptr) return head;
        int cur = head->val;
          // 初始化
        bool flag = false;
        ListNode* ct = new ListNode(0);
        ListNode* pnt = ct;
        head = head->next;
          // 遍歷元素
        while (head) {
            int hd = head->val;
               // 判斷當前元素與之前的元素是否相等
            if (hd != cur) {
                   // 之前的元素沒有出現重複
                if (!flag) {
                       // 把之前的元素存入鏈表
                    pnt->next = new ListNode(cur);
                       // 鏈表移動
                    pnt = pnt->next;
                }else flag = false;
                   // 更新之前的元素
                cur = hd;
            }else flag = true;
            head = head->next;
        }
          // 單獨處理最後一個元素
        if (!flag) pnt->next = new ListNode(cur);
        return ct->next;
    }
};

雖然題目當中沒有對解法做出限制，也沒有規定我們必須要在原鏈表上進行處理，但是這種創建新鏈表的方法終歸有繞開問題的嫌疑。所以我們還有第二種解法，就是直面問題，我們維護多個指針，判斷當前位置的下一個元素是否構成重複。如果重複，則刪除掉重複的部分。

正如我們之前所說的那樣，在單向鏈表當中很難刪除當前元素，所以我們 判斷下一個元素是否會構成重複 。如果重複的話，進行刪除要可行許多。這樣也有一個問題就是， 有可能鏈表的第一個元素就是重複的 ，我們沒有辦法找到第一個元素的上一個元素。針對這個問題，我們採用的方法是 人爲給它創造一個元素放在首元素之前 。這樣我們整個流程就可以串起來了，唯一的難點就是編碼了。

我們仔細一些，寫出代碼還是可以的：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 創建一個新的元素放在鏈表頭部，這樣原本第一個元素就是頭指針的下一個元素了
        node = ListNode()
        node.next = head
        # pnt指向新創建的元素
        pnt = node
        
        while pnt.next is not None:
            # cur指向當前位置的下一個位置
            # 我們要做的即判斷cur這個指針的元素是否重複
            cur = pnt.next
            if cur.next is None:
                break
             
            # ptr指向cur的next
            ptr = cur.next
            # 如果ptr和cur相等，那麼出現重複，我們需要跳過所有相等的元素
            if ptr is not None and ptr.val == cur.val:
                while ptr is not None and ptr.val == cur.val:
                    ptr = ptr.next
                pnt.next = ptr
            # 否則說明不重複，移動pnt
            else:
                pnt = pnt.next
                
        # 由於我們開始的時候人爲添加了一個輔助元素
        # 返回的時候要將它去除
        return node.next

總結

這道題的算法很簡單，我想大部分人都能想出解法來，但是要將解法實現並不太容易。這當中用到了很多小技巧，比如我們認爲創建了一個新的頭結點，比如我們將刪除當前元素轉化成了刪除下一個元素等等。這些技巧雖然算不上什麼，但是靈活使用，可以大大降低我們編碼的複雜度，也正是因爲這一點，這題的質量非常高，值得一做。

很多人非常討厭涉及鏈表的問題，覺得鏈表很難操作，容易寫錯，但實際上 這是基本功的很重要的一部分 。很多公司喜歡考察候選人的基本功，提升這方面的能力對於我們應聘或者是工作非常有幫助。

今天的文章到這裏就結束了，如果喜歡本文的話，請來一波 素質三連 ，給我一點支持吧（ 關注、轉發、點贊 ）。

本文使用 mdnice 排版

相關文章