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

原题链接

难度：$middle$

题目描述

给定一个已排序的链表的头 $head$ ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
复制示例输入

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]
复制示例输入

提示：

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

---

算法

(线性扫描) $O(n)$

为了方便处理边界情况，我们定义一个虚拟元素 dummy 指向链表头节点。
然后从前往后扫描整个链表，每次扫描元素相同的一段，如果这段中的元素个数多于1个，则将整段元素直接删除。

时间复杂度

整个链表只扫描一遍，所以时间复杂度是 $O(n)$

C++ 代码

/*** 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 = new ListNode(0, head);auto p = dummy;while (p->next) {auto q = p->next;while (q && p->next->val == q->val) {q = q->next;}if (p->next->next == q) p = p->next;else p->next = q;}return dummy->next;}
};