问各位一道 leetcode 上的题目

[billyzs]

https://leetcode.com/problems/remove-linked-list-elements/

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

一开始用 recursion 写了个解法，碰到长一点的 input 就超时了。去看了一眼大家的 solution ，虽然每行干的啥能看懂，可和在一起就百思不得其解，好比这个：

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 上高手多，我先谢过了

[anexplore]

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

[wshcdr]

关注

[SharkIng]

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

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

[comesx4]

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

[Yc1992]

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

so dummy is cur

[jonnyhsy]

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

[gssdromen]

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

[billyzs]

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

[domty]

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

[EPr2hh6LADQWqRVH]

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

[billyzs]

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

[mengzhuo]

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

[billyzs]

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

[domty]

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

[Yc1992]

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

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

[phx13ye]

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

[SharkIng]

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

[Andiry]

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

[billryan]

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]

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