这个反向链表的递归函数是如何工作的？

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。反向链表：

给定单链表的头，反向该列表，并返回反向列表。

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

当你看最后一个状态时，你确实看到这些是反向列表的头和尾。

所以，现在，我们知道：

null

null

一种迭代方法是在沿着列表前进的同时保留前一个节点的引用，并重新链接每个下一个引用。以下是LeetCode挑战的工作原理（没有End参考）：

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