求助，用递归去反转链表

[raingorain]

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

所以发了这个贴请教一下 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

[reus]

@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]

@reus 真搞笑你，前面是递归的展开（在全部展开之前还没进行过一次处理），后面才是处理，代码里面进行递归是在反转（后面的三行代码）的前面的，你看不到还是看不懂。本来探讨问题有错误没什么，你这说话的口气真大，口气大有真本事也忍了，关键是你自己没本事还一直 diss 别人，别丢人了行吗？

还先处理 [1], 你自己在纸上写一写看是不是先处理[1], 真是丢人丢到家了

[bucky]

@reus 你仔细看看，仔细想想，想明白了给其他人道个歉

[iceheart]

看我写这个吧，刚出炉
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]

@bucky 我对“处理”的理解，就是调用 reverseList，你对“处理”的理解是改变 next。“先处理[1]”是哪里来的？我有说过？这个帖子就你说了[1]吧？
不争了，没意义。

[Justin13]

递归是很优雅的实现方式，也很好理解。
核心是把公共的处理逻辑抽出来，以递归的方式实现遍历，结束递归的条件就是遍历结束的条件。
有些语言根本没有循环五路，像 for，while 这些都用递归来实现。

[bucky]

@reus 要点脸行吗？自己错了就开始狡辩，递归里面什么时候是式子的展开，什么时候是处理是你说的算吗？真搞笑，就你这水平就别出来丢人了，现在 v 站什么人都感回答问题，你是做销售的吧

[bucky]

@reus 我和一个做销售的讲什么递归，真是浪费时间

[flight2006]

@reus 你这人真喜欢给人扣帽子，就你懂递归，head 就是当前处理节点的引用，链表不是单纯数字的 list 还有节点的 next 指向，那三步就是在反转当前处理 head 的 next 指向问题，代码后面的注释箭头很清楚了

[Deville]

别吵了，PHP 是世界上最好的语言

[xilixjd]

@BingoXuan 画三个节点在纸上，跟着代码过一遍，你连动手都不舍得，自己又不是那种聪明绝顶抽象能力很好的，看再多的资料有啥用？楼上回答基本不用看了，因为看了我感觉你依然想象不出来

[inoki]

@Deville 对的，PHP 是最好的语言。PHP 反转 array 函数的本质就是反转链表[狗头]

[reus]

@flight2006 你说的这些和我说的，有什么冲突吗？

[BingoXuan]

@xilixjd
我没说想象不出来啊，反转链表，二叉树遍历这一类基础本身就不难。lz 代码又不多，嵌套一层也就 14 行代码。只是我习惯就是除非真的太难，否则不会动笔。自我挑战时烧脑的感觉也是很有意思。

[ECHO777]

要理解递归的过程中挂起的概念，这一点很重要

[loryyang]

你自己画一下就知道了啊。如果画不出来，你就中间 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]

@loryyang 谢谢你，真的很用心，现在一个个 node 都 print 出来看了，谢谢

[loryyang]

另外，我看了下，@reus 的说明是对的，别的不清楚在质疑什么
按照我的理解，reus 的解释还是比较容易理解的。next_node 是否要命名为 last_node 看你从什么角度看吧
当然每个人思维方式不一样，建议 lz 自己画一画

[loryyang]

@raingorain 客气，希望你能不断成长，路还很长

[reus]

@bucky 我觉得你这种可以容忍简历造假的人，没有资格鄙视销售。