CODEWITHSUNDEEP
clinked-listreverse
Java Enthusiast
Java Enthusiast

Reputation: 1191

Reversing a Singly Linked List

I know there are multiple questions on the same problem on SO. But somewhere, I am not able to get the logic.

The function that reverses the Linked List is as follows:

void reverse()
{
    struct node *curr=head, *prev=NULL;
    while(curr!=NULL)
    {
        curr->next = prev;
        prev = curr;
        curr = curr->next;
    }
    head = prev;
}

I am using a global head pointer and the structure of a node in the linked list is:

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

struct node *head = NULL;

Here, every time the curr node will point to the prev node and at the end when the list is traversed by the curr node, prev node will point to the last node in the list which I make as the head pointer.

But, this logic doesn't reverse the list and only prints the first node. So, I think the code is executed only once but I am not able to catch the mistake.

The other functions to make the program complete:

#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;
     printf("\n The List is : ");
     while(temp!=NULL)
     {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
}

void reverse()
{
    struct node *curr=head, *prev=NULL;
    while(curr!=NULL)
    {
        curr->next = prev;
        prev = curr;
        curr = curr->next;
    }
    head = prev;
}

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

Upvotes: 2

Views: 274

Answers (1)

kaylum
kaylum

Reputation: 14046

You are overwriting the curr->next pointer which is then used to iterate the list. Code should be more like this:

void reverse()
{
    struct node *curr=head, *prev=NULL;
    struct node *next;
    while(curr!=NULL)
    {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

Upvotes: 5

Related Questions