长大后想做什么？做回小孩！

0%

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

发表于 分类于 Valine：
本文字数： 304

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

GVpMh6.png

思路一：快慢指针 本题是NO.83删除排序链表中的重复元素的姊妹题，区别在于当出现重复的时候将发生重复的节点全部删除。

慢指针slow指向哑节点，fast指向head并遍历链表。

如果fast节点的值等于fast下一个节点的值则继续遍历。

否则值不相等或者fast已到达结尾的时候有两种情况：

  1. fast和slow不相邻，指针之间存在重复的元素，则删除发生重复的节点，即slow.next=fast.next。

    GVn2yn.png

  2. fast和slow相邻，则移动slow到fast的位置。

    GVngQs.png

循环直至fast遍历链表完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode deleteDuplicates(ListNode head) {
    if (head==null||head.next==null)return head;
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    ListNode fast=head,slow=dummy;
    while (fast != null) {
        //如果fast和下一个节点的值不同或者fast到达链尾，有两种情况
        if (fast.next == null || fast.val != fast.next.val) {
            //指针相邻
            if (slow.next == fast) {
                slow=fast;
            }else {//指针不相邻，删除中间的发生重复的节点
                slow.next=fast.next;
            }
        }
        fast=fast.next;
    }
    return dummy.next;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github