系列索引 ： 【刷题笔记0】系列目录索引（持续更新 & 推荐收藏）

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

分类： 链表

难度： 中等

老规矩，先上AC图：

题目：

82. 删除排序链表中的重复元素 II（点击直达原网站）

示例 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)，其中 n 是链表的长度；  空间复杂度： O(1).

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。主要思想就是：一边遍历、一边统计相邻节点的值是否相等，如果值相等就继续后移找到值不等的位置，然后删除值相等的这个区间。

具体实现细节需要注意： 由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node） newHead 指向链表的头节点。

（这里注意，一般如果需要对链表的头节点进行处理，一般都需要在链表头节点之前安排一个新的哑节点（dummy node））

具体地，定义一个指针 node 指向链表的哑节点作为标记重复结点的前结点（永远放到链表没有遍历的结点之前），定义一个指针 bar 指向链表的头节点 head 作为标记重复结点的尾，随后开始对链表进行遍历。如果当前 bar -> next 与 bar -> next -> next 对应的元素相同，所以bar 继续后移，一直找到 bar -> val != bar -> next -> val  ，此时的 bar -> next  就是值不等的节点。此时，我们将链表中所有元素值为 node -> val 的节点全部删除，也就是其中所有 node 和 bar 之间结点删除，也就是 node->next = bar->next，node 直接指向 bar下个结点（中间的就舍去了），之后bar也后移一位，处理下一组数。

如果判断之后，bar没有后移，也就是说node->next == bar，当前 bar -> val != bar -> next -> val 对应的元素不相同，那么说明链表中只有一个元素值为bar -> val 的节点，那么我们就可以将 node 和 bar分别往后移一位，处理下一结点。

当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 return newHead -> next; 即可。

注意： 

• 需要注意 bar 以及bar -> next 可能为空节点，如果不加以判断，可能会产生运行错误。
• 注意下面C++ 代码中并没有释放被删除的链表节点以及哑节点的空间。如果在面试中遇到本题，读者需要针对这一细节与面试官进行沟通。

代码如下：

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">