CODEWITHSUNDEEP
crecursionlinked-list
Java Enthusiast
Java Enthusiast

Reputation: 1191

Reversing a linked list recursively in C

I was trying to write a program to recursively reverse a singly linked list. My logic was to use two pointers prev and head. These two pointers are used to link two nodes in a linked list at a time. But I am not able to determine the base case for the recursive function.

Here is my code:

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

struct node
{
    int data;
    struct node *next;
};

struct node *head = NULL;

void add(int n)
{
    struct node *temp = (struct node*)malloc(sizeof(struct node));
     temp->data = n;
     temp->next = NULL;
     if(head == NULL)
    {
        head = temp;
        return;
     }
    temp->next = head;
    head = temp;
}

void print()
{
    struct node *temp = head;
     putchar('\n');
     printf("The List is : ");
     while(temp!=NULL)
     {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
}

void reverse(struct node *prev, struct node *head)
{
    head->next = prev;
    if(head->next == NULL)
    {
        /* To make the last node pointer as NULL and determine the head pointer */
        return;
    }
    reverse(prev->next, head->next);
}


int main(void)
{
    add(1);
    add(2);
    add(3);
    add(4);
    add(5);
    print();
    reverse(NULL, head);
    print();
    return 0;
}

enter image description here

Upvotes: 1

Views: 913

Answers (1)

simon_xia
simon_xia

Reputation: 2544

You need save head->next first, and then call the func revserse recursively.

Besides, you cannot judge head->next, it maybe null

struct node* reverse(struct node *prev, struct node *head)
{
    if(head == NULL)
    {
        /* To make the last node pointer as NULL and determine the head pointer */
        return prev;
    }
    struct node * next = head->next;
    head->next = prev;
    return reverse(head, next);
}

and then, reset the global var head, because you have reverse the list, the old head points to the tail node now 

head = reverse(NULL, head);

Upvotes: 4

Related Questions