这个递归函数是如何反向链接列表的？

Question

我发现下面的函数递归地反转了链接列表：

def recursive(self, head, end):
    if not head:
        return None, None
    if head.next == end:
        head.next = None
        return head, head
    newHead, newEnd = self.recursive(head.next, end)
    newEnd.next = head
    head.next = None
    return newHead, head

我理解涵盖大小写的if语句。

但我不明白这种重复关系。

递归是如何逆转列表的呢？是否有更简单的递归版本来反转链接列表？作为参考，我正在解决LeetCode问题206.反向链表。

给定单链接列表的head，反转列表，并返回反向列表。

Answer 1

我不明白这种重复关系。

假设我们有一个链接列表：

 head                                                  end
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │ next: ———————→ ...more nodes...——→ │ next:null │
└───────────┘    └───────────┘                        └───────────┘ 

递归部分基于以下观察：

如果您可以反转一个比当前head节点短一个元素的列表，那么我们应该会遇到这样的情况：

 head                                                  end
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │           │                        │           │
│           │    │ next:null │ ←——...more nodes...←———————— :next │ 
└───────────┘    └───────────┘                        └───────────┘ 
                   ↑                                    ↑
                  newEnd                               newHead

在现阶段，我们不怀疑它是如何做到这一点的。我们只是假设它适用于递归情况。因此，如果它正确工作，我们应该得到上面的状态的列表。

现在剩下的语句将链接到当前的head节点，以便它完成包含此节点的列表的反转工作：

newEnd.next = head

这就产生了这样的状态：

 head                                                  end
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next: ———————→ │           │                        │           │
│           │ ←——————— :next │ ←——...more nodes...←———————— :next │ 
└───────────┘    └───────────┘                        └───────────┘ 
                   ↑                                    ↑
                  newEnd                               newHead

然后我们执行：

head.next = None

这两个分配使当前的head成为从递归返回的反向列表的尾节点：

 head                                                  end
  ↓                                                     ↓
┌───────────┐    ┌───────────┐                        ┌───────────┐
│ value: 85 │    │ value: 15 │                        │ value: 20 │
│ next:null │ ←——————— :next │ ←——...more nodes...←———————— :next │ 
└───────────┘    └───────────┘                        └───────────┘ 
                   ↑                                    ↑
                  newEnd                               newHead

现在，我们只需要告诉调用者，它是这个反向列表的头和尾节点：

return newHead, head

当你看最后一种状态时，你会发现它们确实是倒序列表的头尾。

现在，我们知道：

• 基本案例起作用了(你已经很清楚了)
• 递归案例的工作条件是递归正确地返回不包括第一个节点的列表的反向列表。

通过归纳，您可以看到，如果它适用于只有一个节点的列表，那么它也适用于具有2、3、...etc的列表。

备注

• 链接到的LeetCode问题不使用end引用，因此不需要使用它们。
• 递归有其局限性。当列表很长时，可能会遇到堆栈溢出异常。

迭代方法是在遍历列表并重新链接每个next引用时保留对前一个节点的引用。以下是LeetCode挑战的工作原理(没有end引用)：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        while head:
            head.next, prev, head = prev, head, head.next
        return prev

Answer 2

实际上，我不明白这个功能。首先，您应该只需要将列表的头传递给这样一个函数；我不知道为什么要传递参数结束，或者为什么需要传递它。此外，参数self表明，这是一个未显示的类定义的一部分。让我们重新开始：

下面是一个简单的类，用于定义一个节点，该节点可以链接到另一个节点，并使用“名称”进行标识。我们还包括一个小函数，用于遍历链接列表以打印节点：

class Node:
    def __init__(self, name):
        self.name = name
        self.next = None

a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
a.next = b
b.next = c
c.next = d
d.next = e

def print_list(head):
    while head:
        print(head.name)
        head = head.next

print_list(a)

指纹：

A
B
C
D
E

接下来，我们将介绍一个递归函数来反转这样的列表。此函数被传递给列表的head节点，断言不是None。在算法的每一步，我都试图将其解释为注释。一个关键点是注释7：使我们所指的回到了现在，。这涉及到注释5：，我们现在指向None，因为当我们设置head.next = None时，只有当该节点是整个列表的头节点时，它才会保持None。否则，根据注释7，它将在稍后被更新，以指向前一个节点。

def reverse(head):
    assert(head) # 1. make sure head is not None
    next_head = head.next # 2. get the next node, if any
    if next_head is None: # 3. if we do not point to a next node, then
        return head # 4. just return this node as the new head
    head.next = None # 5. we now point backwards to None
    # 6. otherwise, reverse recursively what we were pointing to and get the new head
    new_head = reverse(next_head)
    # 7. make what we had been pointing to now point back to us:
    next_head.next = head
    # 8. and return the new head
    return new_head

# without comments for clarity:
def reverse_no_comments(head):
    assert(head)
    next_head = head.next
    if next_head is None:
        return head
    head.next = None
    new_head = reverse(next_head)
    next_head.next = head
    return new_head

def print_list(head):
    while head:
        print(head.name)
        head = head.next
        

print('Reversed:')
new_head = reverse(a)
print_list(new_head)

指纹：

Reversed:
E
D
C
B
A