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

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，82. Remove Duplicates from Sorted List II

先看题目描述

6L5vZV.png

大意就是给定一个有序链表，让我们删除里面重复的元素

算法和思路

这题和平常做的链表题目差不多，也不太难

算法流程

定义一个哑节点 dumpy，其 next 指针指向链表头元素 head，定义指针 cur 指向 head，移动 head 进行如下循环：

  • 若 cur 指向节点的值与其下一个节点的值相等，说明这里是重复元素，则移动 cur 直至跳过这部分重复元素，并令初始时 cur 的前一个节点的 next 指针指向当前 cur 节点
  • 否则，移动 cur 指向其下一个节点

重复上述循环直至 cur 到达链表尾部，最后返回 dumpy.next 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dumpy = new ListNode();
        dumpy.next = head;
        ListNode pre = dumpy;
        ListNode cur = head;
        while (cur != null) {
            int val = cur.val;
            if (cur.next != null && val == cur.next.val) {
                while (cur != null && cur.val == val) {
                    cur = cur.next;
                }
                pre.next = cur;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dumpy.next;
    }
}