剑指Offer(五十六):删除链表中重复的结点

2018年1月25日09:20:51 24 8,778 °C
摘要

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。

剑指Offer(五十六):删除链表中重复的结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5。

1、思路

删除重复结点,只需要记录当前结点前的最晚访问过的不重复结点pPre、当前结点pCur、指向当前结点后面的结点pNext的三个指针即可。如果当前节点和它后面的几个结点数值相同,那么这些结点都要被剔除,然后更新pPre和pCur;如果不相同,则直接更新pPre和pCur。

需要考虑的是,如果第一个结点是重复结点我们该怎么办?这里我们分别处理一下就好,如果第一个结点是重复结点,那么就把头指针pHead也更新一下。

2、代码

C++:

Python:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:24   其中:访客  15   博主  9

    • avatar 哈苏地方 来自天朝的朋友 Safari浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

      666

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 7.1.1 MIX 2 Build/NMF26X 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口

          @哈苏地方 感谢支持

        • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4

          pPre用来改变实际指针

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点

              @发文 嗯~

              • avatar selami 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省 移动 0

                @发文 为啥pPre是用来改变实际指针的,而pCur和pNext没有这种功能呢,看了好久就卡在这里,望指点!!!!

              • avatar Lucas 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_0 江苏省苏州市 电信 2

                请问重复的结点不保留,不是还需要delete吗

                  • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

                    @Lucas 链表删除节点,就是让next指针绕过删除的节点。

                  • avatar Jason 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 联通 0

                    想问下,因为生成了三个新的指针,这种空间复杂度是O(1)还是O(n)?

                      • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                        @Jason O(1)哈~

                      • avatar opti 来自天朝的朋友 谷歌浏览器 Windows 10 山东省济南市 山东大学齐鲁软件学院 1

                        真好

                        • avatar opti 来自天朝的朋友 谷歌浏览器 Windows 10 山东省济南市 山东大学齐鲁软件学院 1

                          话说没有delete,那节点空间岂不是浪费了

                            • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                              @opti 有新值来了会覆盖的~

                            • avatar 尖沙咀段坤 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信 1

                              楼主你好,C++版本中【20】ListNode* pCur = pHead; 与后面【34】if(pCur == pHead) 是否矛盾呢?

                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                  @尖沙咀段坤 不矛盾,这个就是为了处理头结点的。

                                    • avatar 尖沙咀段坤 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 电信 1

                                      @Jack Cui 感谢回复!我的意思是前面一句已经设置 pCur与pHead相等,那后面 if 语句肯定成立呀,那else语句是不是永远不会执行呢,不知这样理解有没有问题哈?谢谢!

                                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                          @尖沙咀段坤 pCur = pNext->next,pCur移动的啊。

                                    • avatar 晓晓晓满 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 华中科技大学东校区 1

                                      你好,博主,因为我基础比较差,所以问一个比较愚蠢的问题,哈哈,希望不要被嫌弃。python版本的答案里面的pPre=None,这个None是空值还是空的链表结点呢?为什么后边它可以直接给它的pPre.next赋值呢?

                                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                          @晓晓晓满 pPre和pNext为None,就是空值。一个记录前节点,一个记录后节点。next识链表的结构里定义的,指向的是下一个节点的地址。

                                            • avatar 晓晓晓满 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 华中科技大学东校区 1

                                              @Jack Cui 感谢回答。 可能是我没表达清楚,我的意思是为什么 None不就代表空值吗,它为什么可以使用链表结构定义里的next呢? 还是说这个None也是链表的结构定义的None呀? :sad:

                                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                                  @晓晓晓满 这是初始化为None,后面赋新指了,指向了链表节点后,自然就可以用了啊。

                                                  • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通 2

                                                    @晓晓晓满 我第一遍看时也有疑问,但是当你分析程序流程的时候发现,python中在执行20行之前,23行 肯定 肯定 肯定 被执行过了,所以执行20行也就不是问题了。程序的逻辑还是有点绕。

                                              • avatar 小占同学 谷歌浏览器 Windows 10 IANA 保留地址 1

                                                您好,当测试用例为1->1>1时,
                                                if(pCur == pHead){
                                                pHead = pNext->next;
                                                }
                                                中的pNext->next不就为NULL了么?那方法deleteDuplication最后返回的pHead不也为NULL吗?请指教,谢谢

                                                  • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通 2

                                                    @小占同学 删除该链表中重复的结点,指的是重复的结点不保留。分析代码时候潜意识中想法总是认为是删除重复后保留一个即可,导致看代码很混乱。

                                                  • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通 2

                                                    本题要认真读题,删除该链表中重复的结点,指的是重复的结点不保留。分析代码时候潜意识中想法总是认为是删除重复后保留一个即可,导致看代码很混乱。
                                                    疑问:链表只是单纯删除重复节点,链表中的每个节点都是new出来的。链表删除节点,就是让next指针绕过删除的节点没错,但是被删除的节点不delete,以后即使想用这个节点找都找不到啊,怎么不需要delete呢?