No. 82 - Remove Duplicates from Sorted List II
====


---

## [LeetCode 82 -- Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

### 題目描述

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1.
Before remove duplicate nodes

digraph {
                node [shape = circle];
                rankdir=LR
                node1 [label="3"]
                node2 [label="3"]
                1->2->node1->node2->4->5
}

After remove duplicate nodes.

digraph {
                node [shape = circle];
                rankdir=LR
                1->2->4->5
}

Input: head = [1,2,3,3,4,5]
Output: [1,2,4,5]

---

### 解法

本題的目的是要把在 linked list 中重複的 nodes 移除。

這題的解法概念就是我們另外宣告一個新的 linked list 開頭 `dist` 並把沒有重複的 node 加入這個新的 linked list。

完整的程式碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
      if (!head)
        return head;
      
      ListNode *cur = head;
      ListNode *cmp = head->next;
      ListNode *dist = new ListNode(0);
      bool dup = false;
      
      head = dist;
      
      while (cmp) {
        if (cur->val != cmp->val) {
          if (!dup) {
            dist->next = cur;
            dist = dist->next;
          }
          cur = cmp;
          dup = false;
        }
        else
          dup = true;
        cmp = cmp->next;
      }
      if (!dup) {
        dist->next = cur;
        dist = dist->next;
      }
      dist->next = NULL;
      
      return head->next;
    }
};

首先，先宣告一個記錄當前 node 的指標 `cur`，這個 `cur` 紀錄的 node 要被判斷是否可以加入新的 linked list。判斷的方法就是我們有另一個指標 `cmp` 以及一個紀錄是否有重複的 flag `dup`，`cmp` 指標會訪問 `cur` 所指的 node 後面的 node，如果 `cmp` 跟 `cur` 的 node 的值是相同的，則我們會把 `dup` 設為 `true` 帶表 `cur` 所指的 node 是有其他重複值得 node。

這個 `cmp` 指標還有另一個目的，就是找到下一個 node 跟 `cur` 所指的 node 的值不同。當我們找到不同值的 node，我們就會把 `cur` 指到這個新的 node，繼續新一輪的判斷。

而當 `cmp` 找到新的值的 node 我們也會在這時候透過 `dup` 決定 `cur` 的 node 是否可以加入新的 linked list。

最後當 `cmp` 訪問完整個 linked list 的時候也要做最後一次判斷，否則可能會遺漏還有一個沒有重複的 node 的情況，另外也還要把新的 linked list 最後一個 node 的下一個指標指向 `NULL` 防止其後面還會接到原本 linked list 後面的 node。

### 複雜度分析

在時間複雜度上，我們需要尋訪完整個 linked list 才能分辨有重複跟沒有重複的 node，所以需要 $O(N)$。

而在空間複雜度上，我們指宣告固定數量的變數跟指標，所以是 $O(1)$。