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;
}
}

两种实现效率相同。