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

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

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

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入： head = [1,1,2]
输出： [1,2]
复制代码

示例 2：

输入： head = [1,1,2,3,3]
输出： [1,2,3]
复制代码

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

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

也就是说当出现值相同的元素出现多次的情况，要把这些元素只保留一个

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

所以我们可以在遍历链表的过程中判断当前链表节点的值和它的下一个节点的值是否相同，如果相同，则删除下一个链表节点

如果后续链表节点的值依然相同，则继续删除，直到找到一个值不同的链表节点或者走到链表末尾 null

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

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

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

解题思路如下：

1. 特殊判断当链表为空或者链表中只有一个节点的时候，此时肯定不会存在重复元素，直接返回原链表即可
2. 定义一个指针 pre 初始化指向头节点 head, 另一个指针 next 指向 head.next
3. 当 next 指针不为空时，判断 next 指针指向节点的值是否和 pre 指针指向节点的值相同，如果相同，则说明两节点相同，next 指针向后走，直到找到一个节点，值和 pre 指针指向节点值不同
4. 将 pre.next 指向 next,达到删除中间重复元素的效果
5. 两指针一起向后走，直到 next = null
6. 返回头节点 head 即可

整体过程如下：

代码如下：

var deleteDuplicates = function(head) {
  // 如果是空链表或者只有一个节点，不会存在重复元素，直接返回
  if(head === null || head.next === null) return head;
  // 定义两个指针
  let pre = head,next = head.next;
  // 每次next向后找到和pre val值不同的元素，链接pre=>next
  while(next){
    while(next && next.val===pre.val) next = next.next;
    pre.next = next;
    pre = pre.next;
    next = next?next.next:null;
  }
  return head;
};
复制代码

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

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