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 上高手多,我先谢过了
1
anexplore 2015-11-03 13:40:49 +08:00 1
dummy 用来处理 head.val == val 的情况
|
2
wshcdr 2015-11-03 13:43:03 +08:00
关注
|
3
SharkIng 2015-11-03 13:44:28 +08:00 1
link list 结构问题。
如果你将 cur.next = cur.next.next 了,也就是相当于跳过了 val 这个值 当你 dummy.next = head 的时候,也就是相当于指向了整个 List. 不知道这样解释是不是有点糊里糊涂... 楼下接上吧 |
4
comesx4 2015-11-03 13:45:16 +08:00 1
dummy.next 就是指向的就是 head.相当于在 head 前面加了一个 Node.
|
5
Yc1992 2015-11-03 13:45:31 +08:00 1
python 连续赋值的问题
>>>a = b = 9 >>>a is b True so dummy is cur |
6
jonnyhsy 2015-11-03 13:55:42 +08:00
dummy.next 指向 head 阿,它就是要你返回操作后的链表阿。。。话说, LC 开始收费了, premium 1一年上百刀,真尼玛贵阿!
|
7
gssdromen 2015-11-03 14:03:13 +08:00 1
等于用一个指针指向 head,方便操作
|
9
domty 2015-11-03 14:10:29 +08:00
|
10
EPr2hh6LADQWqRVH 2015-11-03 14:13:20 +08:00
wtf, 这种鬼网站还真有人上啊,现在的学生还真是闲啊
|
12
mengzhuo 2015-11-03 14:20:48 +08:00
因为 dummy.next = head 啊
p.s. 别听楼上那些说刷题浪费时间的。 |
15
Yc1992 2015-11-03 14:56:17 +08:00 1
@billyzs 那样的话 dummy 和 cur 就是两个不同的链表了,显然不行。
dummy 是链表头部, cur 负责循环 dummy 链表的每个节点, cur 最后会遍历到尾节点,不能用作返回值,我们需要返回链表的头部,即 dummy ,我是这样理解的。 |
16
phx13ye 2015-11-03 14:59:02 +08:00 1
dummy 后继是链表头啊,所以 remove 完后,返回 dummy 后继节点
|
17
SharkIng 2015-11-03 16:12:04 +08:00 via Android 1
@billyzs 不是有 while cur.next 么, 相当于 Java 里面的 while cur.next != null
|
18
Andiry 2015-11-03 16:22:18 +08:00
这都看不懂,建议你在纸上自己画个图,好加深理解
|
19
billryan 2015-11-03 18:56:45 +08:00 1
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 |
20
xuyinan503 2015-11-03 22:57:29 +08:00
cur 就是 current 的缩写,都挪到最后头了,肯定不能返回 cur 啊
|
22
chy373180 2015-11-04 09:58:22 +08:00 1
建议看下 python 中的拷贝
|