[82] 删除排序链表中的重复元素 II

常规解法（不利用有序）

details

var deleteDuplicates = function (head) {
    let map = new Map();
    let cur = head;
    while (cur !== null) {
        map.set(cur.val, map.has(cur.val) ? map.get(cur.val) + 1 : 1);
        cur = cur.next;
    }
    let dummy = new ListNode();
    cur = dummy;
    while (head !== null) {
        if (map.get(head.val) === 1) {
            cur.next = head;
            cur = cur.next;
        }
        head = head.next;
    }
    // cur.next 设为 null，以确保新链表的尾部节点不指向任何旧链表的节点。
    cur.next = null;
    return dummy.next;
};

正确解法

details

var deleteDuplicates = function (head) {
    let dummy = new ListNode(0, head);
    let prev = dummy;

    while (head !== null) {
        // 如果当前节点值与下一个节点值相同
        if (head.next !== null && head.val === head.next.val) {
            // 跳过所有具有相同值的节点
            while (head.next !== null && head.val === head.next.val) {
                head = head.next;
            }
            // 连接到下一个不同值的节点
            prev.next = head.next;
        } else {
            prev = prev.next;
        }
        head = head.next;
    }

    return dummy.next;
};