使用递归在C中反向链表

Question

我用 C 编写了以下代码。我是 C 的新手。插入和打印功能似乎工作正常，但当我调用 Reverse 功能时，我得到一个提示，说程序停止工作。我哪里出错了？

//WAP to reverse a Linked List using recursion

#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node* next;
};
struct Node* head;  //global variable

struct Node* Reverse(struct Node* p){
    if(p->next == NULL){  //since for last node link part is null
        head = p;
        printf("break condition");
        return head;
    }
    printf("calling reverse");
    Reverse(p->next);
    struct Node* q = p->next;
    q->next = p;
    p->next = NULL;
}

void Insert(int x){
    struct Node* temp= (struct Node*)malloc(sizeof(struct Node));
    temp->data = x;
    //temp->next = NULL; //redundant
    //if(head!= NULL){
    temp->next = head;  //temp.next will point to null when head is null nd otherwise what head was pointing to
    //}
    head = temp;
}

void Print(){
    struct Node* temp1 = head;  //we dont want tomodify head so store it in atemp. bariable and then traverse
    while(temp1 != NULL){
        printf(" %d", temp1->data);
        temp1= temp1->next;
    }
    printf("\n");
}

int main(){
    struct Node* head = NULL;
    Insert(2);
    Insert(4);
    Insert(5);
    Insert(1);
    Print();
    head = Reverse(head);
    //  Print();
}

Answer 1

上面的程序有两个问题：

1) 你有两个 head 变量。一个是全局变量，一个是main函数的局部变量。该局部变量是传递给 Reverse() 的变量。由于该函数所做的第一件事就是取消引用它，因此程序崩溃了。删除 main() 函数中的局部 head 变量应该可以解决它。

2) Reverse() 在达到退出条件时正确地 returns head 运行，但其余时间会发生什么？它在非退出条件情况下缺少 return 。这是可以解决该问题的差异：

    printf("calling reverse");
-   Reverse(p->next);
+   struct Node* ret;
+   ret = Reverse(p->next);
    struct Node* q = p->next;
    q->next = p;
    p->next = NULL;
+   return ret;

使用递归在C中反向链表

reverse linked list in C using recursion

c

linked-list