【一次遍历】删除排序链表中的重复元素 II

题目

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

---

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

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

解题

方法一：一次遍历

思路

新建一个假头(dummy)连接链表，从假头开始遍历链表，记录重复数字节点区间的前驱节点(beforeCommon)用以删除所有重复数字的节点，记录重复数字节点区间中重复的个数(cnt)。

• 遍历的过程中当前节点的后继节点值与重复数字节点区间中第一个节点值不同表示：
  • 当cnt > 1时是重复数字节点区间 $[beforeCommon.next, curr]$ 已结束，需要删除。
  • 否则，节点 beforeCommon.next 只是单独出现的一个节点，不存在重复，无需操作。
• 重置重复个数 cnt = 1
• 相同则表示重复数字节点区间还未结束，重复个数自增 cnt++，其中：
  • 如果当前节点的后继节点已经是尾节点，且重复个数 cnt > 1，则表明$[beforeCommon.next, tail]$ 是最后一个重复数字节点区间，需要删除，直接令 beforeCommon 为尾节点即可

最后返回假头节点的后继节点即为处理后的链表。

代码

/**
 * 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) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0, head), curr = dummy, beforeCommon = dummy;
        int cnt = 0;
        while(curr.next != null) {
            if (curr.next.val == beforeCommon.next.val) {
                cnt++;
                if (curr.next.next == null && cnt > 1) {
                    beforeCommon.next = null;
                    break;
                }
            } else {
                if (cnt > 1) {
                    beforeCommon.next = curr.next;
                } else {
                    beforeCommon = curr;
                }
                cnt = 1;
            }
            curr = curr.next;
        }

        return dummy.next;
    }
}

更简单的写法

 /**
 * 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) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0, head), curr = dummy;
        while(curr.next != null && curr.next.next != null) {
            if (curr.next.val == curr.next.next.val) {
                int commonVal = curr.next.val;
                while (curr.next != null && curr.next.val == commonVal) {
                    curr.next = curr.next.next;
                }
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}