V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
raingorain
V2EX  ›  编程

求助,用递归去反转链表

  •  
  •   raingorain · 2018-10-18 09:15:18 +08:00 · 4251 次点击
    这是一个创建于 1146 天前的主题,其中的信息可能已经有所发展或是发生改变。

    小弟最近在学习算法和数据结构,奈何经常搞不懂递归的问题,也查阅了不少资料,但还是没搞懂用递归去反转链表

    所以发了这个贴请教一下 v2 上面的大佬,谢谢大家啦

    下面是从 leetcode 看到的 solution

    class Solution:
        def reverseList(self, head):
            if not head or not head.next:
                return head
            
            new_head = self.reverseList(head.next)
            next_node = head.next    #        head -> next_node 
            next_node.next = head    #        head <- next_node 
            head.next = None         # [x] <- head <- next_node 
            return new_head
    

    不能理解的地方是,返回最后一个的节点指针时候这三行代码的意思

    next_node = head.next 
    next_node.next = head 
    head.next = None
    
    48 条回复    2018-10-18 20:58:06 +08:00
    x7395759
        1
    x7395759  
       2018-10-18 09:43:18 +08:00
    递归都是靠悟性的
    swulling
        2
    swulling  
       2018-10-18 09:50:30 +08:00 via iPhone
    恕我眼拙,这个算递归么?不就是正常的遍历反转么
    BingoXuan
        3
    BingoXuan  
       2018-10-18 09:52:09 +08:00
    @swulling
    明显是递归,自己调用自己。
    swulling
        4
    swulling  
       2018-10-18 09:52:53 +08:00 via iPhone
    呀,看错了,中间加了递归……不过这个解太复杂了吧,直接遍历反转就行了,这个递归加的没有意义
    canbingzt
        5
    canbingzt  
       2018-10-18 09:53:59 +08:00
    注释很明显了,前 2 行把 2 个节点反向,第 3 行把节点断开(不然就循环了)
    swulling
        6
    swulling  
       2018-10-18 09:54:04 +08:00 via iPhone
    @BingoXuan 嗯,看错了,不过没必要吧,非递归方法比这个还要短…

    递归有更好的解法
    xilixjd
        7
    xilixjd  
       2018-10-18 10:04:36 +08:00
    从我刷 200 题的菜鸡来看,递归靠悟性,1 楼说的很对
    这边递归只是为了将 new_head 指到最后一个节点
    那三行建议你在纸上画个图就理解了
    BingoXuan
        8
    BingoXuan  
       2018-10-18 10:13:47 +08:00
    head 的实现能给一下吗?

    函数返回的是节点。递归最后调用时候 head.next 是倒数第一个,head 是倒数第二个。第一句用临时变量指向倒数第一个节点(即原下一个节点),第二句是将倒数第二个作为倒数第一个下一个节点(原上一个节点是原下一个节点的下一个节点),第三句是把倒数第二个节点指向一个空(原上一个节点的下一个节点是空),以便最后返回的时候节点末尾是空,以及避免两个节点相互指向。最后返回最后一个节点。然后一路往回走,原第一个节点指向空,原最后一个节点按照原先顺序往回一路指向。

    如果还是想不通就直接把函数代码嵌套一层,打印出来把。
    BingoXuan
        9
    BingoXuan  
       2018-10-18 10:19:57 +08:00
    @xilixjd
    我是直接想象一下先嵌套一层,嵌套那一层是用什么条件实现不递归直接跳出来的,按照这个思路推导递归进去,结束条件,递归出来整个过程的。就是纯想就真的烧脑,如果有笔纸会好很多(但是懒。。。)。
    reus
        10
    reus  
       2018-10-18 10:25:33 +08:00   ❤️ 2
    翻转 [head, n1, n2, n3, ...]
    等于先翻转 [n1, n2, n3, ...] 再把 head 放到最后
    head.next 就是 [n1, n2, n3, ...],翻转就是 reverseList(head.next)
    结果是 [..., n3, n2, n1],注意 head.next 现在仍然指向 n1,也就是最后
    所以,next_node = head.next 等于 next_node 赋值为 n1,也就是末尾的结点
    然后 next_node.next = head,就是构造 [..., n3, n2, n1, head]
    head.next = None,就是把 head 指向 n1 去掉
    就翻转了
    next_node 应该命名为 last_node,这样一看就明白了
    bucky
        11
    bucky  
       2018-10-18 10:30:20 +08:00
    new_head = self.reverseList(head.next) # 除了 head 节点已经反转好的链表

    # 将 head 节点和 head.next 交换 原始 head -> head_next -> None 1 -> 2-> None

    head.next.next = head # head -> head_next -> head 1 -> 2-> 1 存在循环
    head.next = None # head 断开 head_next -> head -> None 1 断开 2-> 1 -> None

    return new_head
    bucky
        12
    bucky  
       2018-10-18 10:36:13 +08:00
    # head.next.next = head 和 next_node = head.next next_node.next = head 效果一样

    # 除了 head 节点已经反转好的链表
    new_head = self.reverseList(head.next)

    # 将 head 节点和 head.next 交换
    # 原始 head -> head_next -> None 1 -> 2 -> None

    # head -> head_next -> head 1 -> 2 -> 1 存在循环

    head.next.next = head

    # head 断开 head_next -> head -> None 1 断开 2-> 1 -> None 这就是反转两个结果的结果
    head.next = None

    return new_head
    reus
        13
    reus  
       2018-10-18 10:36:59 +08:00
    开始是 head -> n1 -> n2 -> ...
    reverseList(head.next)之后是:
    new_head -> ... -> n2 -> n1 <- head
    没有循环,是 head 和 n1 的方向不对,那三行就是将 n1 <- head 改成 n1 -> head
    bucky
        14
    bucky  
       2018-10-18 10:53:30 +08:00
    你只要注意这个递归是从后向前处理的,而不是从前往后处理的就容易理解了,
    比如 [1, 2, 3, 4, 5] 是先处理后面 [4, 5] , 把 [4, 5] 变成 [5, 4], 这就是那三行代码的意思
    SpiderXiantang
        15
    SpiderXiantang  
       2018-10-18 10:57:28 +08:00
    leetcode 60 道小白说一句 学递归之前先理解栈
    reus
        16
    reus  
       2018-10-18 11:05:05 +08:00
    @bucky 你这是错的,错得离谱
    zhaogaz
        17
    zhaogaz  
       2018-10-18 11:07:29 +08:00
    递归的核心是一种递推式,就是能把问题拆成子问题,子问题和现有的问题解法一样,就能用递归写出来了。

    leetcode 我只写了几十道题,没到 100,能总结出来规律的。写多了就会了。
    bucky
        18
    bucky  
       2018-10-18 11:21:04 +08:00
    @reus 别急着否定别人,我的代码是提交过 leetcode 的
    YaphetYin
        19
    YaphetYin  
       2018-10-18 11:27:11 +08:00 via iPhone
    这三句把当前 head 放到反序链表的最后面
    flight2006
        20
    flight2006  
       2018-10-18 11:37:33 +08:00
    @reus 你这思路我看了下是错的,最后三行不是调最后的 head,而是反转每个节点的 next 指向,每次执行出栈都会执行,而不是只执行一次,其他人的思路还没看
    reus
        21
    reus  
       2018-10-18 11:57:50 +08:00
    @flight2006 懂递归吗你?
    例如 [1, 2, 3, 4, 5]
    就是翻转 [2, 3, 4, 5],再把 1 放最后
    翻转 [2, 3, 4, 5],就是翻转 [3, 4, 5], 2 放最后
    翻转 [3, 4, 5] 就是 翻转 [4, 5] ,3 放最后
    翻转 [4, 5],就是翻转 [5],4 放最后
    翻转 [5],就是 [5],4 放最后得到 [5, 4]
    再 3 放最后,得到 [5, 4, 3]
    再 2 放最后,得到 [5, 4, 3, 2]
    再 1 放最后,得到 [5, 4, 3, 2, 1]
    每一步概括起来,就是先翻转除了第一个的余下的列表,然后把第一个放最后
    最后三行就是”把第一个元素放在最后“这个操作
    哪来什么“只执行一次”?

    @bucky [1 2 3 4 5]是先处理 [2 3 4 5],当然最后也会处理到 [4 5]
    bucky
        22
    bucky  
       2018-10-18 12:07:05 +08:00
    @reus 真搞笑你,前面是递归的展开(在全部展开之前还没进行过一次处理),后面才是处理,代码里面进行递归是在反转(后面的三行代码)的前面的,你看不到还是看不懂。本来探讨问题有错误没什么,你这说话的口气真大,口气大有真本事也忍了,关键是你自己没本事还一直 diss 别人,别丢人了行吗?

    还先处理 [1], 你自己在纸上写一写看是不是先处理[1], 真是丢人丢到家了
    bucky
        23
    bucky  
       2018-10-18 12:09:55 +08:00
    @reus 你仔细看看,仔细想想,想明白了给其他人道个歉
    iceheart
        24
    iceheart  
       2018-10-18 12:50:23 +08:00 via Android
    看我写这个吧,刚出炉
    node *revert(node* left, node* right){
    if(!right) return left;
    node* next = right->next;
    right->next = left;
    return revert(right,next);
    }
    //use:
    node *rlist = revert(nullptr, list);
    reus
        25
    reus  
       2018-10-18 12:56:18 +08:00
    @bucky 我对“处理”的理解,就是调用 reverseList,你对“处理”的理解是改变 next。“先处理[1]”是哪里来的?我有说过?这个帖子就你说了[1]吧?
    不争了,没意义。
    Justin13
        26
    Justin13  
       2018-10-18 13:13:33 +08:00 via Android
    递归是很优雅的实现方式,也很好理解。
    核心是把公共的处理逻辑抽出来,以递归的方式实现遍历,结束递归的条件就是遍历结束的条件。
    有些语言根本没有循环五路,像 for,while 这些都用递归来实现。
    bucky
        27
    bucky  
       2018-10-18 13:14:40 +08:00
    @reus 要点脸行吗?自己错了就开始狡辩,递归里面什么时候是式子的展开,什么时候是处理是你说的算吗?真搞笑,就你这水平就别出来丢人了,现在 v 站什么人都感回答问题,你是做销售的吧
    bucky
        28
    bucky  
       2018-10-18 13:16:20 +08:00
    @reus 我和一个做销售的讲什么递归,真是浪费时间
    flight2006
        29
    flight2006  
       2018-10-18 13:25:39 +08:00
    @reus 你这人真喜欢给人扣帽子,就你懂递归,head 就是当前处理节点的引用,链表不是单纯数字的 list 还有节点的 next 指向,那三步就是在反转当前处理 head 的 next 指向问题,代码后面的注释箭头很清楚了
    Deville
        30
    Deville  
       2018-10-18 13:28:46 +08:00
    别吵了,PHP 是世界上最好的语言
    xilixjd
        31
    xilixjd  
       2018-10-18 13:37:16 +08:00
    @BingoXuan 画三个节点在纸上,跟着代码过一遍,你连动手都不舍得,自己又不是那种聪明绝顶抽象能力很好的,看再多的资料有啥用?楼上回答基本不用看了,因为看了我感觉你依然想象不出来
    inoki
        32
    inoki  
       2018-10-18 13:41:03 +08:00 via Android
    @Deville 对的,PHP 是最好的语言。PHP 反转 array 函数的本质就是反转链表[狗头]
    reus
        33
    reus  
       2018-10-18 13:58:00 +08:00
    @flight2006 你说的这些和我说的,有什么冲突吗?
    BingoXuan
        34
    BingoXuan  
       2018-10-18 14:09:51 +08:00
    @xilixjd
    我没说想象不出来啊,反转链表,二叉树遍历这一类基础本身就不难。lz 代码又不多,嵌套一层也就 14 行代码。只是我习惯就是除非真的太难,否则不会动笔。自我挑战时烧脑的感觉也是很有意思。
    ECHO777
        35
    ECHO777  
       2018-10-18 16:17:48 +08:00
    要理解递归的过程中挂起的概念,这一点很重要
    loryyang
        36
    loryyang  
       2018-10-18 16:30:44 +08:00
    你自己画一下就知道了啊。如果画不出来,你就中间 print 出来,看看每个 node 都是谁
    如果这个困难都过不去,感觉算法对你来说还是太难了一点
    至于递归的概念,最重要的就是认定一点:这个函数能帮你搞定什么
    比如例子中是:能帮你反转从 head 开始的链表,那么每次递归就是帮你反转除了 head (也就是 head.next 开始)的所有链表,我们可以称为子链表
    那么你递归调用之后,剩下的就是要把 head 塞到反转之后( self.reverseList(head.next))的链表的尾巴上面去。这个尾巴是什么呢?就是原子链表的头:head.next,原来他是头,现在反转就是尾巴了。(需要注意的是,head.next 依然指向这个节点,即使递归里面做了许多操作)
    所以我们要做的就是把 head,塞到 head.next 的后面去,要做的就是 head.next.next 指向 head,head.next 指向 None (尾巴的后面就没有别的东西了)。所以那三行冗余了,其实就两行:head.next.next = head; head.next = None

    其实理解递归最好的公式还是斐波那契数列,你可以去参考下。这个题目完全没必要递归,违反人类直觉
    raingorain
        37
    raingorain  
    OP
       2018-10-18 16:38:11 +08:00
    @loryyang 谢谢你,真的很用心,现在一个个 node 都 print 出来看了,谢谢
    loryyang
        38
    loryyang  
       2018-10-18 16:42:46 +08:00
    另外,我看了下,@reus 的说明是对的,别的不清楚在质疑什么
    按照我的理解,reus 的解释还是比较容易理解的。next_node 是否要命名为 last_node 看你从什么角度看吧
    当然每个人思维方式不一样,建议 lz 自己画一画
    loryyang
        39
    loryyang  
       2018-10-18 16:44:57 +08:00
    @raingorain 客气,希望你能不断成长,路还很长
    reus
        40
    reus  
       2018-10-18 16:53:23 +08:00
    @bucky 我觉得你这种可以容忍简历造假的人,没有资格鄙视销售。
    bucky
        41
    bucky  
       2018-10-18 20:03:08 +08:00
    @reus 我觉得你这种阅读理解能力低下的人没资格说话
    bucky
        42
    bucky  
       2018-10-18 20:06:19 +08:00
    @reus 一个小问题错了都不敢承认,你真是男人呦,佩服
    bucky
        43
    bucky  
       2018-10-18 20:10:00 +08:00
    @loryyang 一个连递归展开都不清楚,不清楚反转链表的执行从后面还是从前面开始的人,你觉得他说的是对的,那你们好好交流一下
    loryyang
        44
    loryyang  
       2018-10-18 20:18:24 +08:00
    chengluyu
        45
    chengluyu  
       2018-10-18 20:24:42 +08:00
    reverse [] = []
    reverse (x:xs) = reverse xs ++ [x]
    bucky
        46
    bucky  
       2018-10-18 20:37:07 +08:00
    @loryyang 你想表达什么,一个错误的答案的有人点赞,还有你这样的人支持,纠正一下错误不是无意义的争论
    bucky
        47
    bucky  
       2018-10-18 20:39:57 +08:00
    @loryyang 说真的,你们两个应该交个朋友,没理可说了就去翻别人的记录,你们两个这么像不交朋友可惜了,当然可能就是一个人呀,哈哈
    icedx
        48
    icedx  
       2018-10-18 20:58:06 +08:00
    写递归的时候最重要的是头脑清晰
    而且一般能跑通(不 SF) 就能正常工作
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3700 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 211ms · UTC 03:59 · PVG 11:59 · LAX 19:59 · JFK 22:59
    ♥ Do have faith in what you're doing.