网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 82. 删除排序链表中的重复元素 II ，难度为 中等。
Tag : 「链表」
存在一个按升序排列的链表，给你这个链表的头节点 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
- 题目数据保证链表已经按升序排列
基本思路
几乎所有的链表题目，都具有相似的解题思路。
- 建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
- 使用 tail 代表当前有效链表的结尾
- 通过原输入的 head 指针进行链表扫描
我们会确保「进入外层循环时 head 不会与上一节点相同」，因此插入时机：
- head 已经没有下一个节点，head 可以被插入
- head 有一下个节点，但是值与 head 不相同，head 可以被插入
代码：
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; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
拓展
- 如果问题变为「相同节点保留一个」，该如何实现？
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; } } 复制代码
最后
这是我们「刷穿 LeetCode」系列文章的第 No.82 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
