一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 918|回复: 7
收起左侧

[Leetcode] 第82道题,删除链表里重复节点(只要重复,一个都不保留)

[复制链接] |试试Instant~ |关注本帖
找工作啊找工作 发表于 2015-7-21 14:28:51 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
我自己花了两个小时没写出来,因为纠结在如果一开始的几个节点重复的话,那么链表的头结点就要发生变化。我一开始的想法是声明两个节点pre 和 newHead并且pre.val = -1在某些情况下如果pre.val == -1 就证明头结点发生变化相应给newHead赋值返回newHead就好啦(我以为节点的值不会有负数,但是我错了。。)
因为不知道什么情况下会更新newHead,我就卡主了。。。
大脑卡机了2个小时之后我就去看了下别人的代码。。原谅我的意志不坚定。。。
https://leetcode.com/discuss/470 ... o-understand-unique
我参看了这个楼主的答案,但是有个地方我不明白。为什么这个楼主并没有改变head和dummy.next的值,但是却能够all cases passed. 明明只改变了pre 和 node, 难道是链表发生了变化,head或者dummy.next能够默认找到链表的头节点?
还有这个楼主强调了unique,但是我也不知道unique和这道题的关系。
求大神给解释下,拜托了。。
水逼一枚 发表于 2015-7-21 15:47:20 | 显示全部楼层
本帖最后由 水逼一枚 于 2015-7-21 15:53 编辑

你注意看,比如你一开始有重复比如11111123,那么它最后做的是pre.next = node.next;, 这一不做完后实际上dummy.next不就是指向2了吗?这就是新的head了。它的那个node变量就是用来不断往前遍历跳过那些重复的duplicates的nodes, 中间环节循环的结束是跳到了duplicate中的最后一个(或者本身就是Unique的没有duplicates)
然后再继续做的处理, 你画画图理解下。
回复 支持 反对

使用道具 举报

 楼主| 找工作啊找工作 发表于 2015-7-21 23:06:06 | 显示全部楼层
水逼一枚 发表于 2015-7-21 02:47
你注意看,比如你一开始有重复比如11111123,那么它最后做的是pre.next = node.next;, 这一不做完后实际上d ...

太感谢了!!!!
回复 支持 反对

使用道具 举报

354886 发表于 2015-7-21 23:12:21 | 显示全部楼层
借楼问一下,如果面试的时候要求不能使用dummy node怎么办呢?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-7-22 00:53:47 | 显示全部楼层
354886 发表于 2015-7-21 23:12
借楼问一下,如果面试的时候要求不能使用dummy node怎么办呢?

为啥会有这种要求呢?应该不会吧。
回复 支持 反对

使用道具 举报

354886 发表于 2015-7-22 01:11:39 | 显示全部楼层
水逼一枚 发表于 2015-7-22 00:53
为啥会有这种要求呢?应该不会吧。

比如要求不能申请额外空间
回复 支持 反对

使用道具 举报

Jocelyn000 发表于 2015-7-22 01:22:49 | 显示全部楼层
354886 发表于 2015-7-22 01:11
比如要求不能申请额外空间

要求in space一般指的是不能建hashmap之类的,tmp node这种应该不算额外空间的
回复 支持 反对

使用道具 举报

354886 发表于 2015-7-22 01:39:08 | 显示全部楼层
Jocelyn000 发表于 2015-7-22 01:22
要求in space一般指的是不能建hashmap之类的,tmp node这种应该不算额外空间的

那如果不用dummy node还有别的做法吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 21:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表