[数据结构与算法] 【LeetCode】83. 删除排序链表中的重复元素

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【LeetCode】83. 删除排序链表中的重复元素 -> 正文阅读

[数据结构与算法]【LeetCode】83. 删除排序链表中的重复元素

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

原题链接： 83. 删除排序链表中的重复元素

题目大意

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。
示例：
在这里插入图片描述
数据范围：

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

思路

开一个虚拟头结点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，只保留一个重复元素。

源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1); // 虚拟头结点
        dummy->next = head;

        auto p = dummy; // 维护一个答案数组，p相当于尾部节点的位置
        while(p->next){
            auto q = p->next; // q为哨兵，若有一连串的重复元素，则q移动至最右侧
            while(q->next && q->next->val == p->next->val) q = q->next;
            if(p->next = q) p = q; // 连续元素只有一个，只需右移p
            else p->next = q;
        }

        return dummy->next;

        
    }
};