[NC]24. 删除有序链表中重复的元素-II

🚩传送门：牛客题目

题目

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为 , 返回
给出的链表为 , 返回

数据范围：链表长度 0≤n≤10000，链表中的值满足 ∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1

输入：{1,2,2} 返回值：{1}

示例2

输入：{} 返回值：{}

解题思路：一次遍历

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。

• pre 指向已经处理后未重复部分的末尾结点，
• cur 指向当前判断结点
• next 指向当前判断结点的下一个结点

  若 next 和 cur 值相等，则 next 后移 **next=next.next** 直至 next=null 或者值不等于 cur 此时将 **pre.next=next** 删除所有重复的红色部分

  若 next 和 cur 值不等，则 pre ，cur ，next 依次后移

当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next 即可。

复杂度分析

时间复杂度： ，其中 是链表的长度。

空间复杂度：

🚩我的代码

public ListNode deleteDuplicates (ListNode head) {
    // 判空
    if(head==null)return head;
    // 初始化
    ListNode dump=new ListNode(-1,head);
    ListNode pre=dump;
    ListNode cur=head;
    ListNode next=head.next;
    // 处理直至结尾
    while(next!=null){
        // 若相等
        if(cur.val==next.val){
            // 直至 next=null 或者值不等于 cur  
            while(next!=null&&next.val==cur.val)next=next.next;
            // 舍弃红色的重复部分
            pre.next=next;
            cur=next;
            next=(next==null?null:next.next);
        }
        else{ // 不等,指针依次后移
            pre=cur;
            cur=next;
            next=next.next;
        }
    }
    return dump.next;
}

官方代码

public ListNode deleteDuplicates(ListNode head) {
    // 判空
    if (head == null) return head;
    // 头结点
    ListNode dummy = new ListNode(0, head);
    ListNode cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        if (cur.next.val == cur.next.next.val) {
            int x = cur.next.val;
            while (cur.next != null && cur.next.val == x) {
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;
}