专栏首页程序员维他命图解 LeetCode 链表: 82. Remove Duplicates from Sorted List II

图解 LeetCode 链表: 82. Remove Duplicates from Sorted List II

今天是 LeetCode 算法的 第 1 阶段第 2 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。这道题是上一道的升级版。

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1:Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2:Input: 1->1->1->2->3 Output: 2->3 LeetCode

分析

移除链表中出现过多次的节点,解这道题的思路也是「水管思路」,对水管进行拆分,重组。链表中可能出现多个重复节点,需要把这些重复的节点全部干掉。列表 L1 = 1-> 1-> 2 中第 1 个节点和第 2 个节点重复,移除,把第 3 个节点接到根节点的后面:

列表 L1 = 1-> 1-> 1 中所有节点重复,需要都移除:

代码

因为链表是有序的,重复的节点可能有多个,只有当前节点即不等于上一个节点也不等于下一个节点的值,才不重复,所以遍历的时候需要记住上一个重复的节点。C++ 实现如下:

结果

Runtime: 8 ms, faster than 100.00% of C++ online submissions for Remove Duplicates from Sorted List II. Memory Usage: 9.3 MB, less than 13.11% of C++ online submissions for Remove Duplicates from Sorted List II.

总结

如果把链表换成数组,你是不是就觉得非常简单了呢?由于单链表不能直接获取某个节点的上一个节点,所以我们创建了一个节点用来记录上一个节点,避免多次遍历。

下一道题目留给你思考:

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 LeetCode

本文分享自微信公众号 - 程序员维他命(J_Knight_)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hash操作

    如果只需要存储元素(或者删除重复元素),无需其他信息,则使用集合,python和c++都是使用set。

    木又AI帮
  • malloc函数分配内存失败的常见原因

    malloc()函数分配内存失败的常见原因: 1. 内存不足。 2. 在前面的程序中出现了内存的越界访问,导致malloc()分配函数所涉及的一些信息被...

    用户1215536
  • 【快学springboot】6.WebMvcConfigurer配置静态资源和解决跨域

    有个朋友说:为什么我配置了WebMvcConfigurer,静态资源static依然能访问?!

    Happyjava
  • 23岁的Python,这些年在编程语言排行榜上直线上升的原因是什么?很多人都不解

    python这些年在编程语言排行榜上名次一直在上升,这个并不是偶然。python发展了几十年,中间好长一段时间无人问津,现在已经发展很成熟了,像新的语言go很多...

    一墨编程学习
  • QML知识-使用Qt信号和方法

    在实际中开发QML应用,会经常用到信号这一属性。像onClicked,onDoubleClicked是异步操作,它们多由信号触发完成。有时候需要与Qt/...

    Qt君
  • 【刨根问底】java静态

    由于今天一个小伙伴问静态static修饰的方法怎么使用,于是联想到,如果你还不会使用或者只是停留在使用层面,那么这里告诉你,静态可没你想的那么简单,比如下面的这...

    用户4143945
  • 水平滚动条

    主要用到并排Div 的父级设置white-space: nowrap,并排的div设置display:inline-block;

    tianyawhl
  • VC++6.0单文件版及安装版,希望能帮助到需要的童鞋!

    相信很多的大家能看到这篇文章的童鞋要么是学生,要么是学习语言汇编的。嗯大部分都是学生,号主我也是从学生时代过来的,在大学期间相信大家都有学习一门叫做C语言的课程...

    FreeRonin
  • 数据结构 | 每日一练(114)

    ——老子

    闫小林
  • C++的类型转换

    (1) static_cast会在编译的过程中进行安全性检查, 相对与dynamic_cast是静态转换;

    Qt君

扫码关注云+社区

领取腾讯云代金券