当前位置: 首页 > article >正文

删除拼排序链表中的重复元素(最优解)

题目来源

82. 删除排序链表中的重复元素 II - 力扣(LeetCode)


题目描述

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

示例 1:

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

示例 2:

输入:head = [1,1,1,2,3]
输出:[2,3]

提示:

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

题目限制

最优解实现题目的解决


思路分析

在处理这个问题时,我们面对的是一个已排序的链表,要求删除所有重复数字的节点,只保留不同的数字。解题的关键在于利用链表已排序这一特性,通过一次遍历完成节点的删除操作。

1. 哨兵节点的引入

  • 由于链表的头节点可能会被删除(例如输入链表 [1,1,2] 时,头节点 1 会被删除),所以引入一个哨兵节点(dummy node)。这个哨兵节点的值可以是任意值,但其作用是作为链表的新头,始终指向第一个不重复的节点。这样在处理链表头节点的删除操作时,就无需特殊处理,简化了代码逻辑。

2. 双指针遍历

  • 我们使用两个指针,一个指针 prev 初始指向哨兵节点,另一个指针 curr 指向链表的头节点 head
  • curr 指针用于遍历链表,prev 指针则用于记录当前不重复节点的前一个节点。在遍历过程中,curr 指针不断前进,同时检查 curr 及其后续节点的值是否与当前 curr 的值相同。

3. 重复节点的处理

  • 当发现 curr 的值与下一个节点的值相同时,说明存在重复节点。此时,curr 指针需要不断向后移动,直到找到一个与当前值不同的节点,这样就跳过了所有重复的节点。
  • 例如,链表为 [1,1,1,2,3],当 curr 指向第一个 1 时,发现下一个节点也是 1curr 就一直移动到值为 2 的节点,此时 curr 指向了 2
  • 然后,将 prev 的 next 指针直接指向 curr,这样就跳过了所有重复的节点。即 prev 原本指向哨兵节点,现在将其 next 指向 2,从而删除了所有值为 1 的节点。

4. 指针移动

  • 在处理完重复节点后,prev 指针移动到 curr 所在位置,因为 curr 现在指向的是一个新的不重复节点。而 curr 指针继续向前移动,准备检查下一组节点。

5. 结束条件

  • 当 curr 指针遍历完整个链表,即 curr 为 null 时,遍历结束。此时,哨兵节点 dummy 的 next 指针指向的链表就是删除所有重复节点后的结果链表,直接返回 dummy.next 即可。

通过这种方法,我们能够在一次遍历链表的过程中,有效地删除所有重复节点,时间复杂度为 ,其中  是链表的长度。同时,由于只使用了有限的额外指针,空间复杂度为 。这种方法简洁高效,充分利用了链表已排序的特性。


具体代码

/**
 * 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) {
        if(!head)return head;
        ListNode* cur=new ListNode(-1);
        cur->next=head;
        ListNode* pre=cur;
        while(cur->next&&cur->next->next)
        {
            if(cur->next->val==cur->next->next->val)
            {
                int c=cur->next->val;
                while(cur->next&&cur->next->val==c)
                {cur->next=cur->next->next;}
            }
            else {cur=cur->next;}
        }return pre->next;
    }
};

这段 C++ 代码定义了Solution类中的deleteDuplicates函数,用于删除已排序链表中重复数字的节点。先判断链表是否为空,空则直接返回。接着创建一个值为 -1 的哨兵节点cur,其next指向原链表头headpre指向cur。通过while循环,当cur的下一个及下下个节点存在时,若二者值相等,记录该值并跳过所有相同值的节点;否则cur后移。最后返回prenext,即删除重复节点后的链表头。


http://www.kler.cn/a/455352.html

相关文章:

  • JVM学习-内存结构(一)
  • 119.【C语言】数据结构之快速排序(调用库函数)
  • HuaWei、NVIDIA 数据中心 AI 算力对比
  • Go+chromedp实现Web UI自动化测试
  • 【ES6复习笔记】Spread 扩展运算符(8)
  • Numpy指南:解锁Python多维数组与矩阵运算(上)
  • [python SQLAlchemy数据库操作入门]-13.集成Pandas:强大的数据分析工具
  • Ubuntu20.04安装FastRTPS,报错没有fastrtps-config.cmake
  • Spring Boot 实战:构建一个简单的 Web 应用
  • PyTorch Lightning模块介绍
  • 在 Vue3 项目中安装和配置 Three.js
  • 磁盘 IO 报警,MySQL 读写哪个文件慢了?
  • C语言简单测试总结
  • 复习打卡大数据篇——Hadoop MapReduce
  • MySQL 高级操作全解析
  • EXCEL中给某一列数据加上双引号
  • 题解:CF286A Lucky Permutation
  • wangEditor富文本插件在vue项目中使用和媒体上传的实现
  • provider-10000模块、consumer-80[RestTemplate远程调用]
  • QT线程 QtConcurrent (深入理解)
  • GCC编译器
  • 全局webSocket 单个页面进行监听并移除单页面监听
  • 【test】git clone lfs问题记录
  • 从VLM到VLA概论
  • SAQ可持续发展评级最新消息
  • Milvus 中,FieldSchema 的 dim 参数和索引参数中的 “nlist“ 的区别