📃 题目描述

题目链接：82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

🔔 解题思路

使用两个指针，一个指针指向某段重复元素的前驱节点，另一个指针用来扫描重复元素。当遇到重复出现的节点时，直接遍历到该重复节点的末尾，然后删除两个指针中间这一段重复节点。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 添加一个头节点，方便处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
		
        // 指向重复元素的前驱节点
        ListNode pre = dummy;
        // 扫描重复元素
        ListNode cur = head;
        while (cur != null) {
            // 遇到重复出现的节点
            if (cur.next != null && cur.val == cur.next.val) {
                // 循环遍历到该重复节点的末尾
                while (cur != null && cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 删除中间这一段重复节点
                cur = cur.next;
                pre.next = cur;
                // 删完这段重复元素后不能更新 pre，因为很有可能现在的 cur.next 又是一段重复元素
                // 比如 1 3 3 4 4, pre = 1, 删完 3 后，cur.next = 4，如果更新 pre 为 cur.next = 4 的话，显然是不合题意的（重复元素需要全部删除）
            } 
            else {
                pre = cur;
                cur = pre.next;
            }
        }
        
        return dummy.next;
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)