Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

Analyze

思路: 快慢指针, 用快指针跳过有重复值的链表, 慢指针负责和快指针拼接! 思路比较精妙, 后面值得二刷。

s cur/q                     // s: slow; q: quick
    1 -> 1 -> 1 -> 2 -> 3
              .
              .
s->cur        q
    1 -> 1 -> 1 -> 2 -> 3
              .
              .
        next
s --------------->cur/q
    1 -> 1 -> 1 -> 2 -> 3
              .
              .
                   s   cur/q
    1 -> 1 -> 1 -> 2 -> 3
              .
              .
                        s
    1 -> 1 -> 1 -> 2 -> 3

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  const dummyHead = new ListNode(0)
  dummyHead.next = head

  let slowPoint = dummyHead

  while(slowPoint.next) {
    let cur = slowPoint.next
    let quickPoint = cur
    while(quickPoint.next && quickPoint.next.val === cur.val) {
      quickPoint = quickPoint.next
    }

    if (cur === quickPoint) {
      slowPoint = slowPoint.next
    } else {
      slowPoint.next = quickPoint.next
    }
  }

  return dummyHead.next
}