reverse linked list in C using recursion

Question

I have written following code in C. I am pretty new to C. The insert and Print functions seem to work fine but I get a prompt that says program stopped working when I call Reverse function. Where dis I go wrong ?

//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();
}

You may want to start by using the Reverse return value for something. Right now the head assignment in main() has no determinate value and your program invokes undefined behavior because all but the last-recursed Reverse call performs no return at all. — WhozCraig
– WhozCraig, Commented Apr 27, 2015 at 2:12

Frederik Deweerdt · Accepted Answer · 2015-04-27 02:13:17Z

3

There are two issues with the program above:

1) You have two head variables. One is a global variable, and the other is a variable local to the main function. That local variable is the one that is passed to Reverse(). Since the first thing that function does is dereferencing it, the program crashes. Removing the local head variable in the main() function should address it.

2) The Reverse() function correctly returns head when it reaches the exit condition, but what happens the rest of the time? It's missing a return in the non-exit condition case. Here's a diff that would address the issue:

    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;

answered Apr 27, 2015 at 2:13

Frederik Deweerdt

5,3512 gold badges32 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

simar kaur Over a year ago

I still have q query though. What really is the use of returning something in non exit condition ? How does that make any difference in this example?head as a global variable was modified in exit condition and hence we returned it but what it the use of returning rest of the times?

Frederik Deweerdt Over a year ago

The calls to Reverse() are recursive. That means that the first call to Reverse() calls Reverse() which calls Reverse() etc.. until the exit condition is reached. When it is reached the last function returns head, which will cause all successive functions to return head until it is returned to the original caller. If you want my opinion, I think that that part is unnecessary in your program, since the head is stored in a global variable anyway.

Collectives™ on Stack Overflow

reverse linked list in C using recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related