求助，用递归去反转链表

[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 指向，每次执行出栈都会执行，而不是只执行一次，其他人的思路还没看