📘 題目敘述
給定一個已經按照遞增順序排序好的 linked list head。
請把所有有重複出現的數字節點全部刪掉，只保留原本 linked list 中那些只出現一次的數字。
最後回傳刪除後的 linked list，並且仍然保持排序。
條件限制
- linked list 的節點數量範圍是
[0, 300] -100 <= Node.val <= 100- linked list 保證已經按照遞增順序排列
🧠 解題思路
我這題的想法是用一個 dummy 節點，讓我可以統一處理「開頭就出現重複」這種情況。
因為題目不是只把重複的多餘節點刪掉，而是要把整段重複值全部刪掉。
所以當我看到某個數字開始重複時，我要做的不是只跳過一個，而是要整段都略過，直接把前面的指標接到下一個不同的數字。
我這份寫法裡：
p會停在目前已經確定保留區段的最後一個位置now會拿來往前掃，看看p->next開頭這一段有沒有重複- 如果有重複，就把整段都跳過
- 如果沒有重複，就讓
p正常往前走一格
因為 linked list 已經排序好，所以相同的數字一定會連在一起，這樣就可以一次判斷一整段。
所有變數
dummy：額外建立的假頭節點，讓刪除開頭重複節點時也能統一處理p：目前保留鏈結串列中的前一個節點，負責接到下一段該保留的位置now：從p->next開始往後掃描，用來檢查某個數值是不是有重複num：目前正在檢查的數值check：記錄目前這段數值是否有出現重複
🪜 主要流程步驟
1. 先建立 dummy 節點，方便處理開頭被刪掉的情況
我先建立一個 dummy，讓它指向原本的 head：
ListNode dummy(0, head);
ListNode* p = &dummy;
這樣做的好處是，如果原本 linked list 的前面幾個節點就全部要被刪掉，
我也不需要特別分情況處理，最後只要回傳 dummy.next 就可以。
2. 每次從 p->next 開始檢查下一段數字
在迴圈裡，我先拿：
ListNode* now = p->next;
這表示我要檢查的是 p 後面那一段。
如果 now 已經是空指標，就代表後面沒有節點了，直接結束：
接著我把目前這段要檢查的數值記成：
int num = now->val;
bool check = false;
其中：
num是目前這一段的值check用來記錄這個值是不是有重複出現
3. 往後掃這一整段相同數值，看它是不是重複段
接著我用 while (now) 一直往後掃：
- 我先把
now往後移一格 - 如果下一格還存在，而且值跟
num一樣，表示這個數字至少重複了，於是把check設成true - 一旦遇到不同值，或走到尾端，就代表這一整段
num已經掃完了
因為 linked list 已經排序，所以相同數字一定是連續出現的。
所以只要這樣一路往後掃，就能知道目前這段是不是重複段。
4. 如果這段有重複，就整段跳過
如果 check == true，就表示目前這個值不是只出現一次，而是重複值。
題目要求這種值要全部刪掉，所以我做的是：
if (check) {
p->next = now;
}
這裡的 now 已經停在：
- 第一個不同值的節點
- 或者
nullptr
所以把 p->next 直接接到 now，
就等於把中間那整段重複值全部跳過了。
5. 如果這段沒有重複，就把 p 往前移
如果 check == false，代表 p->next 這個節點的值只出現一次，應該保留下來。
所以這時候我就讓 p 往前移一格：
else {
p = p->next;
}
這表示我正式把這個節點納入保留答案中，
接著再去檢查它後面的下一段。
6. 最後回傳 dummy.next
當整個 linked list 都處理完之後，
真正的新 head 可能不是原本的 head，所以最後要回傳的是：
return dummy.next;
這樣不管原本開頭有沒有被刪掉，都能正確回傳新的 linked list。
⏱️ 複雜度
設 linked list 長度為 n。
- 時間複雜度：
O(n)
每個節點最多只會被掃過一次。 - 空間複雜度：
O(1)
只用了固定數量的額外指標與變數。
💻 程式碼實作
/**
* 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) {
ListNode dummy(0, head);
ListNode* p = &dummy;
while (p) {
ListNode* now = p->next;
if (!now) {
break;
}
int num = now->val;
bool check = false;
while (now) {
now = now->next;
if (now && now->val == num) {
check = true;
} else {
break;
}
}
if (check) {
p->next = now;
} else {
p = p->next;
}
}
return dummy.next;
}
};
🔗 題目連結
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/