【LeetCode】82. 删除排序链表中的重复元素 II

• • 题目大意
  • 思路
  • • 源代码
  • 类似题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例：

数据范围：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

思路与83. 删除排序链表中的重复元素相同，区别仅在于该题不保留重复元素p->next=q->next，83保留一个重复元素p->next=q。

• 开一个虚拟头结点dummy，从dummy的下一个节点开始开拓答案链表，利用哨兵检查新结点的重复情况，其中dummy的作用在于兼容头结点head也重复的情况。
• 具体地，先令p为dummy，相当于维护一个答案链表，p相当于尾部节点的位置。
• 开拓链表
  从p->next开始，哨兵q检查重复情况，若与p->next重复则继续往右移动。
  移动结束后，若q与p->next相同，则说明p->next不存在与后续节点重复的情况，则p右移到p->next；若q与p->next不相同，则说明从p->next到q均为重复元素，因此令p->next=q->next，不保留重复元素。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // if(!head || !head->next) return head;
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy; // p相当于答案数组的尾结点，而head可能是重复的，因此需要虚拟头结点
        while(p->next){
            auto q = p->next;
            while(q->next && q->next->val == p->next->val) q = q->next;
            if(p->next == q) p = q;
            else p->next = q->next; //改为p->next = q;则为题I
        }

        return dummy->next;

    }
};

时间复杂度：O(n)

看完本文，你可以解决如下题目：
26. 删除有序数组中的重复项
80. 删除有序数组中的重复项 II
83. 删除排序链表中的重复元素