链表反递

Question

我在stanford库中查看下面的代码:

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指向最后一个节点反向休息列表.因此first -> next -> next将是反向休息列表的最后一个节点的下一个指针.现在我们需要指出first我们这样做:

first -> next -> next = first;

在此步骤之后,列表如下所示:

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

现在next列表的最后一个节点的字段必须是NULL.但现在情况并非如此.next最后一个节点(节点1)的字段指向它之前的节点(节点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.