删除排序链表中的重复元素II（82）

题目

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

示例

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

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

算法

单次扫描

创建哨兵节点sentinel，将指针node指向哨兵节点，然后我们向后扫描节点，直到node.next或者node.next.next不存在：

• 如果node.next和node.next.next的值不相同，那么我们后移node一位，继续重复判断
• 如果node.next和node.next.next的值相同，说明node之后的节点重复了需要移除，（即node.next将指向下一个不重复的节点），所以我们创建notSame指针指向node.next.next并向后扫描下一个不重复的值。notSame找到下一个不重复的节点或者指向null时停止，此时我们将node.next指向notSame然后继续重复判断

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const deleteDuplicates = (head) => {
	if (!head || !head.next) return head;
	let sentinel = new ListNode();
	sentinel.next = head;
	let node = sentinel;
	while (node.next && node.next.next) {
		if (node.next.val !== node.next.next.val) {
			node = node.next;
		} else {
			let notSame = node.next.next;
			while (notSame && notSame.val === node.next.val) {
				notSame = notSame.next;
			}
			node.next = notSame;
		}
	}
	return sentinel.next;
};