链表递归反向

Question

我看了下面来自斯坦福图书馆的代码：

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，那么对于最后一个递归步骤，first将是1，rest将是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指向第一个节点，rest指向first旁边的节点。

因为列表不是空的，并且列表不包含一个节点，所以我们递归地调用reverse来反转rest所指向的列表。这是颠倒列表其余部分后列表的外观：

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

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

现在，我们需要将第一个节点附加到反向rest列表的末尾。要将任何内容追加到列表的末尾，我们需要访问列表的最后一个节点。在这种情况下，我们需要访问反向rest列表的最后一个节点。看图，first -> next指向最后一个反转的节点-rest列表。因此，first -> next -> next将是反转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之前被递归地颠倒。