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

题目

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例

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

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

算法

注意这里是排序链表，所以可以使用下面哨兵节点的方法

哨兵节点

prev指针指向哨兵节点，cur指向head，然后比较prev和cur的值，如果prev的值和cur的值相同，那么将cur向后移动一位然后将prev.next指向cur；否则同时向后移动两个指针

直到cur的值为null时，返回哨兵节点sentinel的下一个位置

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const deleteDuplicates = (head) => {
	let sentinel = new ListNode(NaN);
	sentinel.next = head;
	let prev = sentinel,
		cur = head;
	while (cur) {
		if (prev.val === cur.val) {
			cur = cur.next;
			prev.next = cur;
		} else {
			prev = cur;
			cur = cur.next;
		}
	}
	return sentinel.next;
};

数组去重

将链表的所有值取出放在数组中，使用set去重后再生成一个新链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const deleteDuplicates = (head) => {
	const arr = [];
	while (head) {
		arr.push(head.val);
		head = head.next;
	}
	const noRepetition = [...new Set(arr)];
	let listHead = new ListNode();
	noRepHead = listHead;
	noRepetition.forEach((item) => {
		listHead.next = new ListNode(item);
		listHead = listHead.next;
	});
	listHead.next = null;
	return noRepHead.next;
};