如何使用递归交换链表中的相邻节点

Question

我有以下Leetocode问题的解决方案：https://leetcode.com/problems/swap-nodes-in-pairs/

它只是交换链表中的相邻节点。

def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# Nodes to be swapped
first_node = head
second_node = head.next
# Swapping
first_node.next  = self.swapPairs(second_node.next)
second_node.next = first_node
# Now the head is the second node
return second_node

我正在努力在输入上实现递归，所以假设我们有输入节点N1、N2、N3、N4。

当我们应用递归函数时，我得到：

N1 ->SwapPair(N3) ; with second_node = N2 
N3->None ; with second_node = N4

然后当我们解开它时，我得到：

N2-> N1-> N3 ->N4 

正确答案当然是N2-> N1-> N4 ->N3

我不太明白N1是如何与N4相连的——有什么想法吗？

Answer 1

这可能有助于可视化您给出的示例所发生的情况。重要的是要认识到，这个递归函数的每个执行上下文都有自己的一组局部变量。尽管不同的执行上下文的变量名称相同，但它们是不同的。

在主通话中，我们有：

head
↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  
│ val: 1  │  │ val: 2  │  │ val: 3  │  │ val: 4  │
│ next: ───> │ next: ───> │ next: ───> │ next: ───> None
└─────────┘  └─────────┘  └─────────┘  └─────────┘
↑            ↑ 
first_node    second_node

然后发生递归调用，它有自己的变量(名称相同，但不同(：

head
↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  
│ val: 1  │  │ val: 2  │  │ val: 3  │  │ val: 4  │
│ next: ───> │ next: ───> │ next: ───> │ next: ───> None
└─────────┘  └─────────┘  └─────────┘  └─────────┘
↑            ↑ 
first_node   second_node

这里有一个更深层次的递归调用，它也有自己的head变量，即None

head
↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  
│ val: 1  │  │ val: 2  │  │ val: 3  │  │ val: 4  │
│ next: ───> │ next: ───> │ next: ───> │ next: ───> None
└─────────┘  └─────────┘  └─────────┘  └─────────┘

它从第一个CCD_ 5块返回CCD_。

剩下的递归调用返回这个None返回值，并将其分配给first_node.next:

head
↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val: 1  │  │ val: 2  │  │ val: 3  │  │ val: 4  │
│ next: ───> │ next: ───> │ next: ───┐ │ next: ───> None
└─────────┘  └─────────┘  └─────────┘│ └─────────┘   ^
↑        └───────────────┘ 
first_node    ↑ 
second_node

然后执行second_node.next = first_node：

head    ┌──────────────┐
↓      V              │ 
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐│
│ val: 1  │  │ val: 2  │  │ val: 3  │  │ val: 4  ││
│ next: ───> │ next: ───> │ next: ───┐ │ next: ───┘   None
└─────────┘  └─────────┘  └─────────┘│ └─────────┘     ^
↑        └─────────────────┘
first_node    ↑ 
second_node

让我们重新排序最后两个节点的可视化，而不更改任何引用：

head   
↓      
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val: 1  │  │ val: 2  │  │ val: 4  │  │ val: 3  │
│ next: ───> │ next: ───┐ │ next: ───> │ next: ───> None
└─────────┘  └─────────┘│ └─────────┘  └─────────┘
│                ^
└────────────────┘
↑            ↑                
second_node  first_node

然后second_node从递归调用中返回，因此我们返回到第一个执行上下文(带有它自己的局部变量(，在那里first_node.next被分配了返回值：

head      ┌────────────────┐
↓        │                V
┌─────────┐│ ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val: 1  ││ │ val: 2  │  │ val: 4  │  │ val: 3  │
│ next: ───┘ │ next: ───┐ │ next: ───> │ next: ───> None
└─────────┘  └─────────┘│ └─────────┘  └─────────┘
│                ^
└────────────────┘
↑            ↑            ↑           
first_node   second_node  returned

然后执行second_node.next = first_node：

head      ┌────────────────┐
↓        │                V
┌─────────┐│ ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val: 1  ││ │ val: 2  │  │ val: 4  │  │ val: 3  │
│ next: ───┘ │ next: ───┐ │ next: ───> │ next: ───> None
└─────────┘  └─────────┘│ └─────────┘  └─────────┘
^                │
└────────────────┘
↑            ↑
first_node   second_node  

让我们在不更改参考的情况下再次重新排序可视化：

head
↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  
│ val: 2  │  │ val: 1  │  │ val: 4  │  │ val: 3  │
│ next: ───> │ next: ───> │ next: ───> │ next: ───> None
└─────────┘  └─────────┘  └─────────┘  └─────────┘
↑            ↑
second_node  first_node  

最后，返回second_node作为新的头。