删除排序链表中的重复元素 II 图解题解

这道题到底在问什么

输入

1→2→3→3→3→4→4→5

输出

1→2→5

最优解：一步一步想明白

1. 3很多人会和 LC83「删除重复元素」搞混：那题重复值留一个，这题重复值全删光。差一个字，写法完全不同。
2. 4头节点本身可能就是重复值要被删（如 1→1→2）。在最前面焊一个永不被删的哑节点 dummy，让 prev 有稳定落脚点，cur 去往后探路。最后返回 dummy.next。
3. 5dummy.next = head最左边的 D 就是哑节点 dummy。prev 先站在 dummy 上，因为 dummy 一定保留。
4. 6cur = 1cur 指向第一个真节点 1。比较 cur(1) 和它的下一个 cur.next(2) 是否相等。
5. 7确定保留 11 和 2 不相等，说明 1 是独苗、确定保留（标绿）。该让 prev 跟上来了。
6. 8prev=1, cur=2prev 前移到 1，cur 前移到 2。再比较 cur(2) 和 cur.next(3)。
7. 9确定保留 22 和 3 也不相等，2 同样是独苗，保留（标绿）。注意：下面要起波澜了。
8. 10prev=2, cur=第一个3prev 移到 2，cur 移到第一个 3。比较 cur(3) 和 cur.next(3)。
9. 11发现重复 val=3cur(3) 和 cur.next(3) 相等！发现重复值 3。这时一个 3 都不能留，先把第一个 3 标红（待删），记下值 3，让 cur 往后吃。
10. 12while cur.val == 3内层小循环：只要 cur 的值还是 3，cur 就往后走。cur 走到第二个 3，它也标红待删。
11. 13while cur.val == 3值还是 3，继续走。cur 走到第三个 3，三个 3 全部标红，都将被删掉。
12. 14cur.val=4 ≠ 3，循环停cur 再往后，现在指向 4，值不再是 3，内层循环停。此刻三个 3 都夹在 prev(2) 和 cur(4) 之间，等着被一刀切掉。
13. 152 → 4 直连关键一刀：让 prev.next 直接指向 cur。2 后面直接接 4，三个 3 被整段绕过、彻底从链表消失。注意 prev 没有前移——它还要继续盯下一段。
14. 16发现重复 val=4再看 cur(4) 和 cur.next(4)，又相等！重复值 4 出现。同样套路：把所有 4 全删，先把第一个 4 标红。
15. 17while cur.val == 4cur 继续往后吞，走到第二个 4，它也标红。两个 4 都待删。
16. 18cur.val=5 ≠ 4，循环停cur 走到 5，值不是 4 了，停。两个 4 都标红，又夹在 prev(2) 和 cur(5) 之间。
17. 192 → 5 直连再让 prev.next 指向 cur，2 后面直接接 5，两个 4 整段消失。现在链表是 D→1→2→5，cur 指向 5，prev 仍不动。
18. 205 是独苗保留cur(5) 后面是 null，没有下一个可比，说明 5 不重复、保留（标绿）。这一支走 else 分支，prev 和 cur 都要前移。
19. 21cur = nullprev 前移到 5，cur 走到 null（已离开链表，不再显示）。外层 while 的条件不再满足。
20. 22answer = 1→2→5cur 已为 null，循环结束。返回 dummy.next，也就是 1→2→5，正是答案。哑节点 D 完成使命，可以丢掉了。
21. 25一句话记住：prev 永远停在「确定要留」的节点上；cur 去前面探路，一旦发现重复就把那一整片同值节点全部跳掉。
22. 271 1 2 → 头被删输入 1→1→2：开头两个 1 都要删。多亏有哑节点 D，prev 稳站在 D 上，删完后 D.next 直接指向 2，结果是 2。要是没 dummy，头被删了根本不知道该返回谁。
23. 281 1 1 → 全空输入 1→1→1：三个 1 全是重复，整段删光，链表变空。dummy.next 指向 null，返回空链表。算法天然处理这种极端情况。
24. 36这题学完别乱跳，去 链表专题 连刷同类题；卡住时可以随时在页面里提问「为什么这一步成立」，比只背答案更稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        cur = head
        while cur:
            if cur.next and cur.val == cur.next.val:
                val = cur.val
                while cur and cur.val == val:
                    cur = cur.next
                prev.next = cur
            else:
                prev = cur
                cur = cur.next
        return dummy.next

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        ListNode* cur = head;
        while (cur) {
            if (cur->next && cur->val == cur->next->val) {
                int val = cur->val;
                while (cur && cur->val == val)
                    cur = cur->next;
                prev->next = cur;
            } else {
                prev = cur;
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int val = cur.val;
                while (cur != null && cur.val == val)
                    cur = cur.next;
                prev.next = cur;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

# 链表删除题先固定：dummy、prev、cur
dummy = ListNode(0); dummy.next = head
prev, cur = dummy, head
while cur:
    if 需要删除以 cur 开头的一段:
        while 还在这一段里: cur = cur.next
        prev.next = cur          # 整段绕过
    else:
        prev = cur; cur = cur.next
return dummy.next

// 链表删除题先固定：dummy、prev、cur
ListNode dummy(0); dummy.next = head;
ListNode* prev = &dummy; ListNode* cur = head;
while (cur) {
    if (需要删除以 cur 开头的一段) {
        while (还在这一段里) cur = cur->next;
        prev->next = cur;        // 整段绕过
    } else {
        prev = cur; cur = cur->next;
    }
}
return dummy.next;

// 链表删除题先固定：dummy、prev、cur
ListNode dummy = new ListNode(0); dummy.next = head;
ListNode prev = dummy; ListNode cur = head;
while (cur != null) {
    if (需要删除以 cur 开头的一段) {
        while (还在这一段里) cur = cur.next;
        prev.next = cur;         // 整段绕过
    } else {
        prev = cur; cur = cur.next;
    }
}
return dummy.next;

复杂度

面试官可能追问