[路飞]_leetcode-82-删除排序链表中的重复元素 II

「这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

存在一个按升序排列的链表，给你这个链表的头节点 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
• 题目数据保证链表已经按升序排列

本题和 83. 删除排序链表中的重复元素 相似，只是在 83 题的基础上加了那么一丢丢🤏难度

本题要我们删除有序链表中的重复元素

也就是说当出现值相同的元素出现多次的情况，要把这些元素都删除掉

又因为题目给出的链表是有序的，所以值相同的元素一定是连在一起的

所以我们可以在遍历链表的过程中判断是否出现了重复元素

如果出现了重复元素，则把这些重复元素删除，直到链表末尾即可

那在链表中，删除一个节点如何操作呢？

例如：有链表 1=>2=>3=>null，此时如果想要删除链表中 2 号节点，则只需要将链表中 1 号节点的 next 的指针指向 3 号节点，即可达到在该链表中删除 2 号节点的效果

有了以上基础，我们来看下本题如何求解

解题思路如下：

1. 首先特殊判断链表为空或者只有一个节点，直接返回原链表
2. 因为头节点也可能被删除，所以创建虚拟头节点 vhead 方便最后返回结果
3. 初始化 pre 指针指向虚拟头节点 vhead
4. 初始化 cur 指针指向头节点 head
5. 初始化 next 指针指向 head.next
6. 遍历链表，判断 next 指针指向节点值是否等于 cur 指针指向节点值，如果相等，说明出现了重复元素，此时让 next 指针向后走，直到找到第一个不等于 cur 的节点
7. 将 pre.next 指向 next,达到删除 cur 以及重复元素的效果
8. 更新 cur = nextnext = next?next.next:null
9. 链表遍历完成后，返回 vhead.next 即可

整体过程如下：

代码如下：

var deleteDuplicates = function(head) {
  // 特判 链表为空或者只有一个节点，直接返回原链表
  if(head === null || head.next === null) return head;
  // 因为头节点也可能被删除，创建虚拟头节点方便操作
  const vhead = new ListNode(0);
  vhead.next = head;
  // 定义三个指针
  // 重复元素的前一个节点
  let pre = vhead,
  // 重复元素
  cur = head,
  // 重复元素的后一个节点
  next = head.next,
  // 当前是否找到了重复元素
  tag = false;
  // 遍历链表
  while(next){
    // 当 next 不为空并且next的值等于 cur 的值,一直向后走
    while(next && next.val === cur.val){
      // 标记当前 cur 是重复元素
      tag = true;
      next = next.next;
    }
    // 如果 tag 为 true 说明当前 cur 为重复元素，next 为第一个不等于 cur 的元素
    if(tag){
      pre.next = next;
      cur = next;
      next = next?next.next:null;
      tag = false;
    }else{
      // 否则一起向后走，遍历链表
      pre = pre.next;
      cur = cur.next;
      next = next?next.next:null;
    }
  }
  return vhead.next;
};
复制代码

至此我们就完成了 leetcode-82-删除排序链表中的重复元素 II

如有任何问题或建议，欢迎留言讨论！