LC 82. 删除排序链表中的重复元素 II

题目描述

这是 LeetCode 上的 82. 删除排序链表中的重复元素 II ，难度为中等。

存在一个按升序排列的链表，给你这个链表的头节点 head，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1：

1
2
3

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

示例 2：

1
2
3

输入：head = [1,1,1,2,3]

输出：[2,3]

提示：

链表中节点数目在范围 $[0, 300]$ 内
$-100 <= Node.val <= 100$
题目数据保证链表已经按升序排列

基本思路

几乎所有的链表题目，都具有相似的解题思路。

建一个虚拟头节点 dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
使用 tail 代表当前有效链表的结尾
通过原输入的 head 指针进行链表扫描

我们会确保「进入外层循环时 head 不会与上一节点相同」，因此插入时机：

head 已经没有下一个节点，head 可以被插入
head 有一下个节点，但是值与 head 不相同，head 可以被插入

Java 代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (head != null) {
            // 进入循环时，确保了 head 不会与上一节点相同
            if (head.next == null || head.val != head.next.val) {
                tail.next = head;
                tail = head;
            }
            // 如果 head 与下一节点相同，跳过相同节点
            while (head.next != null && head.val == head.next.val) head = head.next;
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }
}

C++ 代码：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        while (head != nullptr) {
            // 进入循环时，确保了 head 不会与上一节点相同
            if (head->next == nullptr || head->val != head->next->val) {
                tail->next = head;
                tail = head;
            }
            // 如果 head 与下一节点相同，跳过相同节点
            while (head->next != nullptr && head->val == head->next->val) head = head->next;
            head = head->next;
        }
        tail->next = nullptr;
        return dummy->next;
    }
};

Python 代码：

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        tail = dummy
        while head:
            # 进入循环时，确保了 head 不会与上一节点相同
            if not head.next or head.val != head.next.val:
                tail.next = head
                tail = head
            # 如果 head 与下一节点相同，跳过相同节点
            while head.next and head.val == head.next.val: head = head.next
            head = head.next
        tail.next = None
        return dummy.next

TypeScript 代码：

function deleteDuplicates(head: ListNode | null): ListNode | null {
    const dummy: ListNode = new ListNode();
    let tail: ListNode | null = dummy;
    while (head) {
        // 进入循环时，确保了 head 不会与上一节点相同
        if (!head.next || head.val !== head.next.val) {
            tail.next = head;
            tail = head;
        }
        // 如果 head 与下一节点相同，跳过相同节点
        while (head.next && head.val === head.next.val) head = head.next;
        head = head.next;
    }
    tail.next = null;
    return dummy.next;
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

拓展

如果问题变为「相同节点保留一个」，该如何实现？

还是类似的解题思路。

建一个虚拟头节点 dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
使用 tail 代表当前有效链表的结尾
通过原输入的 head 指针进行链表扫描

Java 代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}

C++ 代码：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        ListNode* dummy = new ListNode(-109);
        ListNode* tail = dummy;
        while (head) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail->val != head->val) {
                tail->next = head;
                tail = tail->next;
            }
            head = head->next;
        }
        tail->next = nullptr;
        return dummy->next;
    }
};

Python 代码：

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        dummy = ListNode(-109)
        tail = dummy
        while head:
            # 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if tail.val != head.val:
                tail.next = head
                tail = tail.next
            head = head.next
        tail.next = None
        return dummy.next

TypeScript 代码：

function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (!head) return head;
    const dummy: ListNode = new ListNode(-109);
    let tail: ListNode | null = dummy;
    while (head) {
        // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
        if (tail.val !== head.val) {
            tail.next = head;
            tail = tail.next;
        }
        head = head.next;
    }
    tail.next = null;
    return dummy.next;
};

时间复杂度：$O(n)$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.82 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

链表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 83. 删除排序链表中的重复元素上一篇

LC 456. 132 模式下一篇