82. Remove Duplicates from Sorted List II

Leetcode

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

題目

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

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

解答

• 方法一

var deleteDuplicates = function(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    
    let lastNode = dummy;
    let isSame = false;
    while(head) {
        // 如果 next === null，會跑下面的 else，把 lastNode -> null
        if(head.next?.val === head.val) {
            // 刪除下一個重複的數
            isSame = true;
            head.next = head.next.next;
        } else {
            if(isSame) {
                // 將所有重複的數都略過
                lastNode.next = head.next;
                isSame = false;
            } else {
                // 之前沒有刪除過重複的數，lastNode 跟 head 一樣都往前一步
                lastNode = head;
            }
            head = head.next;
        }
    }
    
    return dummy.next;
};

Runtime: 138 ms, faster than 14.63% of JavaScript online submissions for Remove Duplicates from Sorted List II.

Memory Usage: 40.6 MB, less than 50.12% of JavaScript online submissions for Remove Duplicates from Sorted List II.

測資

let head = [1, 1]; // null
head = [1, 2, 2]; // [1]