这个反向链表的递归函数是如何工作的? [英] How does this recursive function to reverse a linked list work?

问题描述

我发现下面的函数可以递归地反转链表:

I found the function below that reverses a linked list recursively:

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 语句.

I understand the if statements that cover for the base case.

但我不明白递归关系.

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

How does that recursion work to reverse the list? Is there a more simple recursive version that reverses a linked list? For reference, I am solving LeetCode problem 206. Reverse Linked List:

给定单向链表的head，反转列表，返回反转后的列表.

Given the head of a singly linked list, reverse the list, and return the reversed list.

推荐答案

我不明白递归关系.

I do not understand the recurrence relation.

假设我们有这个链表:

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

递归部分基于以下观察:

The recursive part is based on the following observation:

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

If you can reverse a list that is one element shorter, which excludes the current head node, then we should arrive in a situation like this:

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

在这个阶段，我们不质疑它是如何做到的.我们只是假设它适用于递归情况.所以如果它正常工作，我们应该得到列表的上述状态.

At this stage we do not question how it did that. We just assume it works for the recursive case. So if it works correctly, we should get the above state of the list.

现在剩余的语句将链接当前的 head 节点，以便它完成对包括这个节点的列表的反转作业:

Now the remaining statements will link the current head node so that it finishes the reversal job for a list that includes this node also:

newEnd.next = head

这会产生这种状态:

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

然后我们执行:

head.next = None

这两个赋值使当前的 head 成为我们从递归返回的反向列表的尾节点:

These two assignments have made the current head a tail node to the reversed list we got back from recursion:

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

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

Now we just need to tell the caller which is the head and tail node of this reversed list:

return newHead, head

当您查看最终状态时，您确实会看到它们是反向列表的头部和尾部.

When you look at the final state, you see indeed that those are the head and tail of the reversed list.

所以，现在，我们知道:

So, now, we know that:

• 基本案例有效(你已经很清楚了)
• 递归情况适用的条件是递归正确返回排除第一个节点的列表的反向列表

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

By induction you can then see that if it works for a list with just one node, it also works for a list with 2, with 3, ...etc.

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

• The LeetCode problem you linked to does not use end references, so you should not need to use them.
• Recursion has its limits. When the list is long, you could run into a stack overflow exception.

一种迭代方法是在您沿列表行走时保留前一个节点的引用并重新链接每个next 引用.下面是 LeetCode 挑战的工作原理(没有 end 参考):

An iterative method is to keep a reference of the preceding node while you walk along the list and relink each next reference. Here is how that works for the LeetCode challenge (no end reference):

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

这篇关于这个反向链表的递归函数是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！