目录
一、前言
删除排序链表中的重复元素II元素这道题，可以说是--链表专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
本片博客就来详细的讲讲解一下 删除排序链表中的重复元素II 的实现方法，让我们的面试变的更加顺利！！！
二、题目描述
给定一个已排序的链表的头
head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表
三、解题方法
⭐ 双指针 -- 采用 哨兵位头节点
🥝 什么是哨兵位头节点？
首先，先来了解一下什么是 哨兵位---头节点 ？
- 它是一个附加的链表结点，该 结点 作为 第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
- 也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。
哨兵位 --- 头节点的作用：
- 比如向链表中插入一个节点，对于没有哨兵位的单链表，当待插入的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
- 如果有哨兵位头节点，则第一个节点的处理方式与其它节点相同，可以统一进行处理。
🍍 解题思路
这道题，其实就是之前讲过的 ---- 删除排序链表中的重复元素 --- 的升级版
- 我们先创建一个 哨兵位的头节点 pre_head , 令 pre_head->next = head , 然后创建 双指针 pre 指向 pre_head ，指针 cur 指向 head , 开始遍历整个链表
- 当 cur 指向的节点值 与 cur->next 指向的节点值相同时，我们就让 cur 不断向后移动，直到 cur 指向的节点值与 cur->next 指向的节点值不相同时，停止移动。
- 此时，我们判断 pre->next 是否等于 cur ，如果相等，说明 pre 与 cur 之间没有重复节点（因为 cur 没有因为有重复节点而向后移动）；否则，说明 pre 与 cur 之间有重复的节点，我们就让 pre->next 指向 cur ->next (跳过重复的元素，重新建立连接)
- 然后让 cur 继续向后移动，继续上述操作，直到 cur 为空，遍历结束
🍍 案例图解
链表：【1，2，3，3，4，4，5】
- 创建 哨兵位头节点 和 双指针，开始遍历整个链表
- cur 与下一个节点 值不同，pre ->next = cur , cur 与 pre之间没有重复元素，pre向前移动
- cur 与下一个节点 值相同，cur 向后移动
- pre ->next != cur 存在重复元素，跳过重复元素，重新建立连接
- cur 与下一个节点 值相同，cur 向后移动
- pre ->next != cur 存在重复元素，跳过重复元素，重新建立连接
- 然后让 cur 继续向后移动，继续上述操作，直到 cur 为空，遍历结束
- 返回 pre_head ->head
代码：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
// 创建一个 哨兵位的 头节点 初始化为 -1 ，并且 连接在 head 之前
ListNode* pre_head = new ListNode(-1,head);
// 双指针
ListNode* pre = pre_head;
ListNode* cur = head;
// 开始遍历整个链表
while(cur)
{
// 寻找 下一个不同值的 节点
while(cur->next && cur->next->val == cur->val)
{
cur = cur->next;
}
// 由于cur 遇到重复 会向后移动 所以 当 pre->next!=cur时，说明有重复元素
// pre 与 cur 之间没有重复的元素
if(pre->next == cur)
{
//没有重复元素时 pre 就向后移动
pre = cur;
}
else // 存在重复的元素
{
// 跳过重复的元素，重建建立连接
pre->next = cur->next;
}
// 更新当前节点
cur = cur->next;
}
// 返回哨兵位 后的头节点
return pre_head->next;
}
};四、总结与提炼
最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关删除排序链表中的重复元素II的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握
五、共勉
以下就是我对 删除排序链表中的重复元素II 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！
