21-05-21-2-删除排序链表中的重复元素

题目地址

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

题目描述

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。例如：1->1->2 => 2

变体：重复的数字中保留下来一个。例如：1->1->2 => 1->2

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/submissions/

思路

• 排序链表中一个节点的值等于前面节点或者等于后面节点，这个节点就是重复的，移除全部这类节点。
• 创建一个哑节点，能够保证head节点也在重复范围内，被删除后能够保证哑节点的next指针就指向调整完的链表的头节点
• 迭代链表，当当前节点的值等于前面节点的或者等于后面节点的时候，就删除该节点。
• 为了删除方便，迭代过程中利用prevNode保存前面节点，当删除节点了，prevNode就不变，迭代了之后那prevNode就还是cur。
• 增加一个变量prevValue保留被删除节点的值或者迭代过去的节点的值，用于快速判断。
• 变体题目与原题差不多，不过这题更简单点 只需要更next比较就行了 因为反正最后都要保留一个。所以在原题的基础上移除掉prevValue的比较和保存的逻辑就行了

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  if (!head || !head.next) return head;
  let cur = head;
  let dummyNode = new ListNode(0);
  dummyNode.next = head;
  let prevNode = dummyNode;
  let prevValue; // 变体注释掉这行
  while (cur) {
    if (
      (prevValue === cur.val) ||
      (cur.next != null && cur.next.val === cur.val) // 变体注释掉这行
    ) {
      let nextNode = cur.next;
      prevNode.next = nextNode;
      prevValue = cur.val; // 变体注释掉这行
      cur.next = null;
      cur = nextNode;
    } else {
      prevNode = cur;
      prevValue = cur.val; // 变体注释掉这行
      cur = cur.next;
    }
  }
  return dummyNode.next;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)