V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
billyzs
V2EX  ›  Python

问各位一道 leetcode 上的题目

  •  
  •   billyzs · 2015-11-03 13:30:13 +08:00 · 3723 次点击
    这是一个创建于 3295 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    22 条回复    2015-11-04 09:58:22 +08:00
    anexplore
        1
    anexplore  
       2015-11-03 13:40:49 +08:00   ❤️ 1
    dummy 用来处理 head.val == val 的情况
    wshcdr
        2
    wshcdr  
       2015-11-03 13:43:03 +08:00
    关注
    SharkIng
        3
    SharkIng  
       2015-11-03 13:44:28 +08:00   ❤️ 1
    link list 结构问题。
    如果你将 cur.next = cur.next.next 了,也就是相当于跳过了 val 这个值
    当你 dummy.next = head 的时候,也就是相当于指向了整个 List.

    不知道这样解释是不是有点糊里糊涂... 楼下接上吧
    comesx4
        4
    comesx4  
       2015-11-03 13:45:16 +08:00   ❤️ 1
    dummy.next 就是指向的就是 head.相当于在 head 前面加了一个 Node.
    Yc1992
        5
    Yc1992  
       2015-11-03 13:45:31 +08:00   ❤️ 1
    python 连续赋值的问题
    >>>a = b = 9
    >>>a is b
    True

    so dummy is cur
    jonnyhsy
        6
    jonnyhsy  
       2015-11-03 13:55:42 +08:00
    dummy.next 指向 head 阿,它就是要你返回操作后的链表阿。。。话说, LC 开始收费了, premium 1一年上百刀,真尼玛贵阿!
    gssdromen
        7
    gssdromen  
       2015-11-03 14:03:13 +08:00   ❤️ 1
    等于用一个指针指向 head,方便操作
    billyzs
        8
    billyzs  
    OP
       2015-11-03 14:08:37 +08:00
    @jonnyhsy 不太理解这个价格。正儿八经有收入的人哪会有大把时间刷 LC
    domty
        9
    domty  
       2015-11-03 14:10:29 +08:00
    @jonnyhsy
    前两天没事想去刷 leetcode 发现收费了
    然后就去刷 lintcode 了
    刷的第一题就是你题的这个....
    EPr2hh6LADQWqRVH
        10
    EPr2hh6LADQWqRVH  
       2015-11-03 14:13:20 +08:00
    wtf, 这种鬼网站还真有人上啊,现在的学生还真是闲啊
    billyzs
        11
    billyzs  
    OP
       2015-11-03 14:20:27 +08:00
    @SharkIng 明白一些了。可是照这么 loop 下去 cur 不就变成 None 了吗
    mengzhuo
        12
    mengzhuo  
       2015-11-03 14:20:48 +08:00
    因为 dummy.next = head 啊
    p.s. 别听楼上那些说刷题浪费时间的。
    billyzs
        13
    billyzs  
    OP
       2015-11-03 14:21:59 +08:00
    @Yc1992 长知识。那么这么做有什么好处吗?只用一个 cur = LN 然后操作 cur 行不行呢
    domty
        14
    domty  
       2015-11-03 14:22:13 +08:00
    @billyzs
    少年 你需要先搞清楚啥叫 引用...
    Yc1992
        15
    Yc1992  
       2015-11-03 14:56:17 +08:00   ❤️ 1
    @billyzs 那样的话 dummy 和 cur 就是两个不同的链表了,显然不行。

    dummy 是链表头部, cur 负责循环 dummy 链表的每个节点, cur 最后会遍历到尾节点,不能用作返回值,我们需要返回链表的头部,即 dummy ,我是这样理解的。
    phx13ye
        16
    phx13ye  
       2015-11-03 14:59:02 +08:00   ❤️ 1
    dummy 后继是链表头啊,所以 remove 完后,返回 dummy 后继节点
    SharkIng
        17
    SharkIng  
       2015-11-03 16:12:04 +08:00 via Android   ❤️ 1
    @billyzs 不是有 while cur.next 么, 相当于 Java 里面的 while cur.next != null
    Andiry
        18
    Andiry  
       2015-11-03 16:22:18 +08:00
    这都看不懂,建议你在纸上自己画个图,好加深理解
    billryan
        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
    xuyinan503
        20
    xuyinan503  
       2015-11-03 22:57:29 +08:00
    cur 就是 current 的缩写,都挪到最后头了,肯定不能返回 cur 啊
    kmahyyg
        21
    kmahyyg  
       2015-11-04 00:24:28 +08:00
    @domty lintcode 咋样?有手机客户端吗?
    chy373180
        22
    chy373180  
       2015-11-04 09:58:22 +08:00   ❤️ 1
    建议看下 python 中的拷贝
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2723 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 08:39 · PVG 16:39 · LAX 00:39 · JFK 03:39
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.