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

2018年1月25日09:20:51 20 4,404 °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
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

目前评论:20   其中:访客  11   博主  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 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 IANA 保留地址 1

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