[LeetCode] 82. 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]

Constraints:
The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

删除排序链表中的重复元素II。

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

思路

题意跟版本一很接近，唯一的区别是，版本一是请你删除重复元素，使得 output 里面每个元素只出现一次。版本二是请你删除所有出现超过一次的元素。思路是需要创建一个 dummy 节点，放在所有需要遍历的节点之前，遍历的时候，找是否有两个节点的 val 相同，找到后记下这个 val。再往后遍历的时候，只要遇到这个 val 就跳过。

比如第一个例子好了，当 cur 遍历到 2 的时候，cur.next == 3, cur.next.next == 3；此时记录 sameVal = cur.next.val。接着从 cur.next 开始判断，只要 cur.next.val == 3 的时候，就 cur.next = cur.next.next。

如果是比如一开始遍历到 1 的时候好了，此时cur.next == 2，cur.next.next == 3，两者并不相等，所以直接就遍历下一个节点，cur = cur.next。

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // corner case
        if (head == null || head.next == null) {
            return head;
        }

        // normal case
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 注意这里cur是从dummy开始
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int sameVal = cur.next.val;
                while (cur.next != null && cur.next.val == sameVal) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

JavaScript实现

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    // corner case
    if (head === null || head.next === null) return head;

    // normal case
    let dummy = new ListNode(0);
    dummy.next = head;
    let cur = dummy;
    while (cur.next !== null && cur.next.next !== null) {
        if (cur.next.val === cur.next.next.val) {
            let sameVal = cur.next.val;
            while (cur.next !== null && cur.next.val === sameVal) {
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;
};

相关题目

83. Remove Duplicates from Sorted List
82. Remove Duplicates from Sorted List II
1836. Remove Duplicates From an Unsorted Linked List