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 ![]() dummy 用来处理 head.val == val 的情况 |
3 SharkIng 2015-11-03 13:44:28 +08:00 ![]() link list 结构问题。 如果你将 cur.next = cur.next.next 了,也就是相当于跳过了 val 这个值 当你 dummy.next = head 的时候,也就是相当于指向了整个 List. 不知道这样解释是不是有点糊里糊涂... 楼下接上吧 |
![]() | 4 comesx4 2015-11-03 13:45:16 +08:00 ![]() dummy.next 就是指向的就是 head.相当于在 head 前面加了一个 Node. |
![]() | 5 Yc1992 2015-11-03 13:45:31 +08:00 ![]() 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 ![]() 等于用一个指针指向 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 ![]() @billyzs 那样的话 dummy 和 cur 就是两个不同的链表了,显然不行。 dummy 是链表头部, cur 负责循环 dummy 链表的每个节点, cur 最后会遍历到尾节点,不能用作返回值,我们需要返回链表的头部,即 dummy ,我是这样理解的。 |
16 phx13ye 2015-11-03 14:59:02 +08:00 ![]() dummy 后继是链表头啊,所以 remove 完后,返回 dummy 后继节点 |
17 SharkIng 2015-11-03 16:12:04 +08:00 via Android ![]() @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. 链表头节点不定的常用技巧,使用 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 ![]() 建议看下 python 中的拷贝 |