递归逆转链表(斯坦福CSed库中的代码)的解释 [英] Recursively reverse a linkedlist (code in Stanford CSed library) explanation

问题描述

我的递归技巧非常生锈.我一直在考虑这个问题，并在论坛上搜索了很长时间，但仍然无法理解.现在，我正在递归地查看Stanford CS ed库中的链表代码.

My recursion skill is pretty rusty. I've been thinking about this problem and searched the forum for a long time but still cannot understand. Right now I'm looking at the recursively reverse a linked list code from Stanford CS ed library.

#include <stdio.h> 

struct Node {
  int x;
  struct Node *next;
};

void Reverse(struct Node ** headRef){
    struct Node* first;
    struct Node* rest;

    if(*headRef==NULL)
       return;

    first= *headRef;
    rest= first->next;  

    if(rest==NULL)
        return; 

    Reverse(&rest);
    printf("Rest%d\n", (rest)->x); // I added this line to print rest
    first->next->next=first;
    first->next=NULL;
    *headRef=rest;
}

void printList(struct Node* head){

    if(!head)
       return;
    else{
       printf("%d ", head->x);
       printList(head->next);   
    }
}

void main(){
    struct Node *head;
    struct Node * node1= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node2= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node3= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node4= (struct Node*) malloc(sizeof(struct Node));
    head= node1;
    node1->next=node2;
    node1->x=1;
    node2->x=2;
    node3->x=3;
    node4->x=4;
    node2->next=node3;
    node3->next=node4;
    node4->next=NULL;
    Reverse(&head);
}

现在假设我有一个链接列表1-> 2-> 3-> 4.我不明白的是最后一行，最终会将headRef设置为4，我认为应该将headRef设置为2.我试图执行该函数并将其打印出来:

Now suppose I have a linked list 1->2->3->4. What I cannot understand is the last line, which will set the headRef to 4 eventually, I think it should set the headRef to 2. I tried to execute the function and it printed out:

4
4
4

4
4
4

用于变量rest.

但是，如果我将反转"功能的最后一行注释掉，它仍会反转列表，但会打印

However, if I commented the last line in the the Reverse function out, it still reversed the list but would print

4
3
2.

4
3
2.

我可以理解的第二个结果，但是第一个结果似乎很令人困惑.语句"* headRef = rest"对变量rest有什么作用吗?它一直指向4是什么?

The second result I can understand, but the first one seemed quite confusing. Does the statement "*headRef=rest" do any thing to the variable rest? What does it keep pointing to 4?

此外，如果我通过* headRef而不是** headRef(最后一行未注释掉)，它将打印结果

Also, if I pass *headRef instead of **headRef (last line is not commented out), it would print the result

4
3
2

4
3
2

也是.

有人可以向我解释一下记忆中发生了什么吗?太感谢了.

Could anyone please explain to me what happened in the memory? Thanks a million.

推荐答案

在递归调用 Reverse 之前，我们有:

Before the recursive call to Reverse we have:

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

在递归调用 Reverse 之后，我们得到:

After the recursive call to Reverse we have:

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

现在，我们需要通过 first-> next-> next = first 将 2-> NULL 修复为 2-> 1 代码>.

Now we need to fix 2->NULL to 2->1 by first->next->next=first.

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

现在我们需要通过 first-> next = NULL 将 1-> 2 修复为 1-> NULL ./p>

Now we need to fix 1->2 to 1->NULL by first->next=NULL.

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

最后 * headRef = rest ，以便 * headRef 指向 4 而不是 1 .

Finally *headRef=rest so that *headRef will point to 4 instead of to 1.

这篇关于递归逆转链表(斯坦福CSed库中的代码)的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！