第82道题，删除链表里重复节点（只要重复，一个都不保留）

我自己花了两个小时没写出来，因为纠结在如果一开始的几个节点重复的话，那么链表的头结点就要发生变化。我一开始的想法是声明两个节点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和这道题的关系。
求大神给解释下，拜托了。。

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

水逼一枚 发表于 2015-7-21 02:47
你注意看，比如你一开始有重复比如11111123，那么它最后做的是pre.next = node.next;, 这一不做完后实际上d ...

太感谢了！！！！

借楼问一下，如果面试的时候要求不能使用dummy node怎么办呢？

354886 发表于 2015-7-21 23:12
借楼问一下，如果面试的时候要求不能使用dummy node怎么办呢？

为啥会有这种要求呢？应该不会吧。

水逼一枚 发表于 2015-7-22 00:53
为啥会有这种要求呢？应该不会吧。

比如要求不能申请额外空间

354886 发表于 2015-7-22 01:11
比如要求不能申请额外空间

要求in space一般指的是不能建hashmap之类的，tmp node这种应该不算额外空间的

Jocelyn000 发表于 2015-7-22 01:22
要求in space一般指的是不能建hashmap之类的，tmp node这种应该不算额外空间的

那如果不用dummy node还有别的做法吗？