82. [M] Remove Duplicates from Sorted List II

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

题目难度在于细节。

为了简化一开始就是连续相同数字这种情况下的逻辑，设置一个空节点做为头节点指向最终结果。

第一版实现，设置前节点 p 、当前节点 c 。

输入 1 1 2 3 3 4

初始：(h/c) -> (1/head) -> (1) -> (2) -> (3) -> (3) -> (4)

第一步：更新 p = c
(h/p/c) -> (1) -> (1) -> (2/c) -> (3) -> (3) -> (4)
第二步：更新 c 指向下一个
(h/p) -> (1/c) -> (1) -> (2) -> (3) -> (3) -> (4)
第三步：如果 c 与下一个节点值相同，则移动 c 至值不同的节点
(h/p) -> (1) -> (1) -> (2/c) -> (3) -> (3) -> (4)
第四步：更新 p.next 指向 c
(h/p) -> (2/c) -> (3) -> (3) -> (4)

重复这个过程

实现代码如下

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode h = new ListNode(-head.val);
        h.next = head;
        ListNode c = h, p = null;
        
        while (c != null) {
            p = c;
            c = c.next;
            while (c != null && c.next != null && c.next.val == c.val) {
                for (int v = c.val; c != null && c.val == v; c = c.next);
            }                               
            p.next = c;
        }
            
        return h.next;
    }
}

重点注意内部的第二个 while ，这是消除类似 3344 这种连续几段相同数字的关键，不能只用一个 if 。结束的时候，c 指向 null ，所以最后一个节点的 next 也是 null 。

第二版实现，用一个计数器计数过去的几个节点有几个相同数字的，如果是 1 则将过去的节点加入到新链表中。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode h = new ListNode(0);
        ListNode p = head, hp = h;
        
        int c, v;
        while (p != null) {
            ListNode t = p;
            for (c = 0, v = p.val; p != null && v == p.val; c++) {
                p = p.next;
            }
            if (c == 1) {
                hp.next = t;
                hp = hp.next;
            }
        }
        hp.next = null;
        
        return h.next;
    }
}

两种实现效率相同。