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

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

中文链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

题目详述

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

示例 1:

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

示例 2:

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

题目详解

与 LeetCode83-删除排序链表中的重复元素 类似，本题改为了删除所有重复的结点。

  • 因为可能删除头结点，为了方便操作，新建了一个 dummy 结点充当头结点。
  • 运用两个指针 pre 和 cur，pre 代表前一个结点，cur 代表待检查的结点。
  • 每次移动 cur，如果不存在重复结点，直接更新 pre 和 cur；存在重复就跳过所有重复结点，让 pre 的 next 指向下一个结点。
  • 重复这个过程，直至到达链表末尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00082 {

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            if (pre.next == cur) {
                pre = cur;              // 没有重复，移动 pre 为当前结点
            } else {
                pre.next = cur.next;    // 存在重复，跳过所有重复的结点
            }
            cur = cur.next;             // 移动到下一结点
        }
        return dummy.next;
    }
}