链表反递

我正在查看斯坦福图书馆的以下代码：

void recursiveReverse(struct node** head_ref) { struct node* first; struct node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* put the first element on the end of the list */ recursiveReverse(&rest); first->next->next = first; /* tricky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; } 

我不明白的是在最后的递归步骤中，例如，如果列表是1-2-3-4现在对于最后一个递归步骤，第一个将是1，其余将是2.所以如果你设置* head_ref = rest ..这使得列表的头部2 ?? 有人可以解释一下如何在倒转列表的头部之后变成4吗？

Answer 1

绘制堆栈跟踪…

 Intial - {1,2,3,4} Head - 1 Rest = 2,3,4 Recurse(2,3,4) Head = 2 Rest = 3,4 Recurse(3,4) Head = 3 Rest = 4 Recurse (4) Head = 4 Rest = null //Base Case Reached!! Unwind. So now we pick up Recurse(3,4) Head = 3 Rest = 4 // Return picks up here first->next->next = first; so list is: 3,4,3 // set head to null, null ,4,3, //Off with his head! 4,3 Return Now we're here Recurse(2,3,4) Head = 2 Rest = 3,4 Previous return leaves state as: Head = 2 //But Head -> next is still 3! -- We haven't changed that yet.. Rest = 4,3 Head->next is 3, Head->next->next = 2 makes the list (actually a tree now) 4->3->2 ^ | 2 And chop off the head leaving 4->3->2 and return. Similarly, do the last step which will leave 4->3->2->1 ^ | 1 and chop off the head, which removes the one. 

Answer 2

考虑清单：

  1 -> 2 -> 3 -> 4 -> NULL ^ ^ | | first rest 

first指向第一个节点，其余指向first节点旁边的节点。

由于列表不为空且列表不包含一个节点，因此我们进行递归调用以reverse以反转rest指向的列表。 这是列表在反转列表的其余部分后的样子：

  1 -> 2 <- 3 <- 4 ^ | ^ | NULL | first rest 

如图所示， rest现在指向反向列表，其中列表的开头为4 ，列表末尾为2 。 节点2的下一个指针是NULL 。

现在我们需要将第一个节点附加到reverse-rest列表的末尾。 要将任何内容附加到列表的末尾，我们需要访问列表的最后一个节点。 在这种情况下，我们需要访问reverse-rest列表的最后一个节点。 查看图表， first -> next指向最后一个节点的反向rest列表。 因此， first -> next -> next将是reverse-rest列表的最后一个节点的下一个指针。 现在我们需要first指出，所以我们做：

 first -> next -> next = first; 

在此步骤之后，列表如下所示：

  1 <- 2 <- 3 <- 4 ^ -> ^ | | first rest 

现在列表的最后一个节点的next字段必须为NULL 。 但现在情况并非如此。 最后一个节点（节点1 ）的next字段指向它之前的节点（节点2 ）。 要解决这个问题，我们会：

 first -> next = NULL; 

在此之后，列表看起来像：

 NULL <- 1 <- 2 <- 3 <- 4 ^ ^ | | first rest 

如图所示，列表现在正确地反转， rest指向反转列表的头部。

我们需要返回新的头指针，以便更改反映在调用函数中。 但这是一个void函数， head作为双指针传递，所以改变*head的值将使调用函数看到改变的头：

 *head = rest; 

Answer 3

剩下的不是2 ，它是2 -> 3 -> 4 ，递归反转。 之后我们将*head_ref设置为rest ，现在（递归反转！） 4 -> 3 -> 2 。

这里重要的一点是，虽然first和rest都有相同的类型，即node* ，但它们在概念上基本上是不同的： first指向一个单独的元素，而rest指向一个链接的元素列表 。 在将链接列表分配给*head_ref之前，递归反转此链接列表。

Answer 4

我最近编写了一个用于在ruby中反转链表的递归方法。 这里是：

 def reverse!( node_1 = @head, node_2 = @head.link ) unless node_2.link node_2.link = node_1 @head = node_2 return node_1 else return_node = reverse!(node_1.link, node_2.link) return_node.link = node_1 node_1.link = nil return node_1 end return self end