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

简介: 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


如有任何问题或建议,欢迎留言讨论!

相关文章
|
3月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
46 1
|
3月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
47 0
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
30 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
34 0
LeetCode第二十四题(两两交换链表中的节点)
|
3月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
112 0
|
8月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
7月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
7月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
7月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
69 2
|
8月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
86 1