14. 删除排序链表中的重复元素 II

题目

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

使用哈希表先存储节点进行计数，再创建一个新的链表返回，这种方式比较简单就不放代码了。

code

// 思路：
//   1 2 2 3 3 4
// p i j
//   p i j
//   p i   j
//-------------------
//   1 3 3 4
//   p i j
//   p i   j
//-------------------
//   1 4
//   p i j
//-----------------
// exit 

function deleteDuplicates(head) {

  if (!head || !head.next) return head

  let prev = null
  let cur = head
  let after = head.next

  // 如果头几个节点连续相同，则先对头结点进行更换处理
  // 比如 1 1 2 3 4
  // 比如 1 1 2 2
  // 比如 1 1 2
  while (after && cur.val === after.val) {
    while (cur.val === after.val) {
      after = after.next
      if (after === null) {
        return null
      }
    }
    cur = after
    after = cur.next
  }

  // 更换头结点
  head = cur

  // 针对这类情况：1 1 2、1 1 1 2 
  if (after === null) {
    return cur
  }

  // 针对这类情况: 1 2 3 4 4 5 5
  while (after) {
    if (cur.val !== after.val) {
      prev = cur
      cur = after
      after = after.next
    } else {
      while (cur.val === after.val) {
        after = after.next
        // 如果after为空了，则说明后面没有节点了，这个时候只需要将prev.next指向空
        // 再直接返回头结点就好了
        if (after === null) {
          prev.next = null
          return head
        }
      }
      prev.next = after
      cur = after
      after = after.next
    }
  }

  return head
};