如何在Python中使用递归方法反转单链表

发布于09月03日

我想知道如何在Python语言中使用递归方法来反转单链表.

给定单链接列表的第head位，反转该列表并返回the reversed list.

例1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

大多数人使用迭代方法，这是非常classic 且易于理解的方法.然而，我遇到了一个令我困惑的递归方法:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # recursive call
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None
        print(newHead)
        return newHead

例如，如果我输入[1，2，3]，我会手动计算出如下过程，这看起来似乎是正确的，但我不能说服自己，它将通过递归调用reverselist返回正确的东西.你能告诉我为什么吗？非常感谢！

推荐答案

以下是如何可视化链接列表1→2→3的逆转:

我们从以下几个方面开始:

 head
  │
┌─┴─────────┐   ┌───────────┐   ┌───────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

第一个递归调用接收head.next，并将有自己的本地名称.为了将这些本地名称与我们在reverseList的原始执行中已经读到的名称区分开来，我将在名称中添加重音符号，其中Accens的数量表示递归深度.因此，在第一次递归调用时，我们可以将情况可视化为:

 head            head'
  │               │
┌─┴─────────┐   ┌─┴─────────┐   ┌───────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

在第二级递归调用中:

 head            head'           head'' newHead''
  │               │               │      │
┌─┴─────────┐   ┌─┴─────────┐   ┌─┴──────┴──┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

这个二级递归执行不会进入if块，只会将head''的next属性设置为None(它已经这样做了)并返回newHead''.

返回第一次返回的引用赋值为newHead'的递归执行，因此我们得到以下结果:

 head            head'           newHead'
  │               │               │
┌─┴─────────┐   ┌─┴─────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘

在这个递归执行中，这是我们第一次执行head.next.next = head，作用于head'.因此，我们得到:

 head            head'           newHead'
  │               │               │
┌─┴─────────┐   ┌─┴─────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ────────┤ next: ┐   │
│           │   │           ├───────────┘   │
└───────────┘   └───────────┘   └───────────┘

然后head'的next属性得到None:

 head            head'           newHead'
  │               │               │
┌─┴─────────┐   ┌─┴─────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: None│   │ next: ┐   │
│           │   │           ├───────────┘   │
└───────────┘   └───────────┘   └───────────┘

最后，第一次递归执行返回newHead'.

原始执行接收此引用并将其分配给自己的newHead:

 head                            newHead
  │                               │
┌─┴─────────┐   ┌───────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: None│   │ next: ┐   │
│           │   │           ├───────────┘   │
└───────────┘   └───────────┘   └───────────┘

同样，执行head.next.next = head:

 head                            newHead
  │                               │
┌─┴─────────┐   ┌───────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: ────────┤ next: ┐   │   │ next: ┐   │
│           ├───────────┘   ├───────────┘   │
└───────────┘   └───────────┘   └───────────┘

最后，将head.next设置为None，并返回newHead:

                                 (returned)
                                  │
┌───────────┐   ┌───────────┐   ┌─┴─────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │
│ next: None│   │ next: ┐   │   │ next: ┐   │
│           ├───────────┘   ├───────────┘   │
└───────────┘   └───────────┘   └───────────┘

...这是颠倒了的名单.

希望这能澄清这一点.