链表递归反向 [英] Linked list recursive reverse

问题描述

我正在查看下面来自斯坦福图书馆的代码:

I was looking at the code below from stanford library:

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;
}

我不明白的是在最后一个递归步骤中，例如 if list is 1-2-3-4 现在最后一个递归步骤首先是 1，其余的将是 2.所以如果你设置 *head_ref =休息 .. 这使得列表的头部 2 ??有人可以解释一下在反转列表的头部后如何变成 4 吗??

What I don't understand is in the last recursive step for e.g if list is 1-2-3-4 Now for the last recursive step first will be 1 and rest will be 2. So if you set *head_ref = rest .. that makes the head of the list 2 ?? Can someone please explain how after reversing the head of the list becomes 4 ??

推荐答案

绘制堆栈跟踪...

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. 

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