问各位一道 leetcode 上的题目

def removeElements(self, head, val):
    dummy = cur = ListNode(0)
    dummy.next = head
    while cur and cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

明明是操作了cur，为什么return dummy.next返回的是正确答案呢？ p2ex 上高手多，我先谢过了

cur

val

return

head

22 条回复 • 2015-11-04 09:58:22 +08:00

anexplore

2015-11-03 13:40:49 +08:00

dummy 用来处理 head.val == val 的情况

wshcdr

2015-11-03 13:43:03 +08:00

关注

SharkIng

2015-11-03 13:44:28 +08:00

link list 结构问题。
如果你将 cur.next = cur.next.next 了，也就是相当于跳过了 val 这个值
当你 dummy.next = head 的时候，也就是相当于指向了整个 List.

不知道这样解释是不是有点糊里糊涂... 楼下接上吧

comesx4

2015-11-03 13:45:16 +08:00

dummy.next 就是指向的就是 head.相当于在 head 前面加了一个 Node.

Yc1992

2015-11-03 13:45:31 +08:00

python 连续赋值的问题
>>>a = b = 9
>>>a is b
True

so dummy is cur

jonnyhsy

2015-11-03 13:55:42 +08:00

dummy.next 指向 head 阿，它就是要你返回操作后的链表阿。。。话说， LC 开始收费了， premium １一年上百刀，真尼玛贵阿！

gssdromen

2015-11-03 14:03:13 +08:00

等于用一个指针指向 head,方便操作

billyzs

2015-11-03 14:08:37 +08:00

@jonnyhsy 不太理解这个价格。正儿八经有收入的人哪会有大把时间刷 LC

domty

2015-11-03 14:10:29 +08:00

@jonnyhsy
前两天没事想去刷 leetcode 发现收费了
然后就去刷 lintcode 了
刷的第一题就是你题的这个....

EPr2hh6LADQWqRVH

2015-11-03 14:13:20 +08:00

wtf, 这种鬼网站还真有人上啊，现在的学生还真是闲啊

billyzs

2015-11-03 14:20:27 +08:00

@SharkIng 明白一些了。可是照这么 loop 下去 cur 不就变成 None 了吗

mengzhuo

2015-11-03 14:20:48 +08:00

因为 dummy.next = head 啊
p.s. 别听楼上那些说刷题浪费时间的。

billyzs

2015-11-03 14:21:59 +08:00

@Yc1992 长知识。那么这么做有什么好处吗？只用一个 cur = LN 然后操作 cur 行不行呢

domty

2015-11-03 14:22:13 +08:00

@billyzs
少年你需要先搞清楚啥叫引用...

Yc1992

2015-11-03 14:56:17 +08:00

@billyzs 那样的话 dummy 和 cur 就是两个不同的链表了，显然不行。

dummy 是链表头部， cur 负责循环 dummy 链表的每个节点， cur 最后会遍历到尾节点，不能用作返回值，我们需要返回链表的头部，即 dummy ，我是这样理解的。

phx13ye

2015-11-03 14:59:02 +08:00

dummy 后继是链表头啊，所以 remove 完后，返回 dummy 后继节点

SharkIng

2015-11-03 16:12:04 +08:00 via Android

@billyzs 不是有 while cur.next 么，相当于 Java 里面的 while cur.next != null

Andiry

2015-11-03 16:22:18 +08:00

这都看不懂，建议你在纸上自己画个图，好加深理解

billryan

2015-11-03 18:56:45 +08:00

1. 链表头节点不定的常用技巧，使用 dummy 节点。
2. 删除链表中的节点，相当于将 next 指向新节点

见 http://algorithm.yuanbin.me/zh-cn/linked_list/remove_linked_list_elements.html

链表的常用方法见 http://algorithm.yuanbin.me/zh-cn/basics_data_structure/linked_list.html

xuyinan503

2015-11-03 22:57:29 +08:00

cur 就是 current 的缩写，都挪到最后头了，肯定不能返回 cur 啊

kmahyyg

2015-11-04 00:24:28 +08:00

@domty lintcode 咋样？有手机客户端吗？

chy373180

2015-11-04 09:58:22 +08:00

建议看下 python 中的拷贝