求助，用递归去反转链表

[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

[x7395759]

递归都是靠悟性的

[swulling]

恕我眼拙，这个算递归么？不就是正常的遍历反转么

[BingoXuan]

@swulling
明显是递归，自己调用自己。

[swulling]

呀，看错了，中间加了递归……不过这个解太复杂了吧，直接遍历反转就行了，这个递归加的没有意义

[canbingzt]

注释很明显了，前 2 行把 2 个节点反向，第 3 行把节点断开（不然就循环了）

[swulling]

@BingoXuan 嗯，看错了，不过没必要吧，非递归方法比这个还要短…

递归有更好的解法

[xilixjd]

从我刷 200 题的菜鸡来看，递归靠悟性，1 楼说的很对
这边递归只是为了将 new_head 指到最后一个节点
那三行建议你在纸上画个图就理解了

[BingoXuan]

head 的实现能给一下吗？

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

如果还是想不通就直接把函数代码嵌套一层，打印出来把。

[BingoXuan]

@xilixjd
我是直接想象一下先嵌套一层，嵌套那一层是用什么条件实现不递归直接跳出来的，按照这个思路推导递归进去，结束条件，递归出来整个过程的。就是纯想就真的烧脑，如果有笔纸会好很多（但是懒。。。）。

[reus]

翻转 [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]

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]

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

开始是 head -> n1 -> n2 -> ...
reverseList(head.next)之后是：
new_head -> ... -> n2 -> n1 <- head
没有循环，是 head 和 n1 的方向不对，那三行就是将 n1 <- head 改成 n1 -> head

[bucky]

你只要注意这个递归是从后向前处理的，而不是从前往后处理的就容易理解了，
比如 [1, 2, 3, 4, 5] 是先处理后面 [4, 5] ， 把 [4, 5] 变成 [5, 4], 这就是那三行代码的意思

[SpiderXiantang]

leetcode 60 道小白说一句 学递归之前先理解栈

[reus]

@bucky 你这是错的，错得离谱

[zhaogaz]

递归的核心是一种递推式，就是能把问题拆成子问题，子问题和现有的问题解法一样，就能用递归写出来了。

leetcode 我只写了几十道题，没到 100，能总结出来规律的。写多了就会了。

[bucky]

@reus 别急着否定别人，我的代码是提交过 leetcode 的

[YaphetYin]

这三句把当前 head 放到反序链表的最后面

[flight2006]

@reus 你这思路我看了下是错的，最后三行不是调最后的 head，而是反转每个节点的 next 指向，每次执行出栈都会执行，而不是只执行一次，其他人的思路还没看

[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 我觉得你这种可以容忍简历造假的人，没有资格鄙视销售。

[bucky]

@reus 我觉得你这种阅读理解能力低下的人没资格说话

[bucky]

@reus 一个小问题错了都不敢承认，你真是男人呦，佩服

[bucky]

@loryyang 一个连递归展开都不清楚，不清楚反转链表的执行从后面还是从前面开始的人，你觉得他说的是对的，那你们好好交流一下

[loryyang]

@bucky https://www.v2ex.com/t/475001#reply48

[chengluyu]

reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

[bucky]

@loryyang 你想表达什么，一个错误的答案的有人点赞，还有你这样的人支持，纠正一下错误不是无意义的争论

[bucky]

@loryyang 说真的，你们两个应该交个朋友，没理可说了就去翻别人的记录，你们两个这么像不交朋友可惜了，当然可能就是一个人呀，哈哈

[icedx]

写递归的时候最重要的是头脑清晰
而且一般能跑通(不 SF) 就能正常工作