Reversing a linked list : C implemenation

For reversing a linked list we have to choice :-

1.  Change all links .
2.  Change the data part .

Second method , changing the data , is very easy !
What we have to do for that is :

• Create a linked list
• Create a stack as well
• In Reverse Function ()
• Push() all the elements in the stack first .
• Now stack contains the elements of linked list in same order.
• Traverse the list from head to NULL again .
• Assign the the popped value to each node .
• As Stack pops elements in reverse order , we'll have a reversed list now . 

check its implementation :

Reversing linked list using stack :

---

#include<stdio.h>
#include<stdlib.h>
#define max 100


// creating a stack of integers

int top=-1;
int stack[max];

void push(int );
int pop();

//linked list part


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

struct node *head=NULL;

void append();
void addatbeg();
void reverse();
void display();

int main()
{
int choice;
while(1){
    printf("Enter your choice:\n");
    printf("1.Append\n2.Add at begining\n3.Display\n4.Reverse\n5.Exit\n");
    scanf("%d",&choice);

        switch(choice)
        {
            case 1:
                append();break;
            case 2:
                addatbeg();break;
            case 3:
                display();break;
            case 4:
                reverse();break;
            case 5:
                return 0;
            default :
                printf("Try valid input\n");
        }
    }
}

void append()
{
    struct node *temp,*trav;
    trav=head;
    temp=(struct node *)malloc(sizeof(struct node));
    int n;
    printf("Enter data to add at end : ");
    scanf("%d",&n);
    temp->data = n;
   
    if(head==NULL)
    {
        temp->link=NULL;
        head=temp;  
    }
    else
    {
        while(trav->link!=NULL)
        {
            trav=trav->link;
        }
        trav->link = temp;
        temp->link = NULL;
    }
   
}


void addatbeg()
{
    struct node *temp;
    temp=head;
    temp=(struct node *)malloc(sizeof(struct node));
    int n;
    printf("Enter data to add at beginning : ");
    scanf("%d",&n);
    temp->data = n;
   
    if(head==NULL)
    {
        temp->link=NULL;
        head=temp;  
    }
   
    else{
        temp->link = head;
        head = temp;
    }
}

void reverse()
{
    //pushing elements in the stack
    struct node *temp;
    temp = head;
    while(temp!=NULL)
    {
        push(temp->data);
        temp=temp->link;
    }
    // poping elements from stack
   
    struct node *temp1;
    temp1=head;
    while(temp1!=NULL)
    {
        temp1->data = pop();
        temp1=temp1->link;
    }
   
    //setting the stack again for further use.
    top=-1;
}


void display()
{
    struct node *temp ;
    temp =head;
    printf("List : ");
    while(temp != NULL)
    {
        printf(" %d ",temp->data);
        temp=temp->link;
    }
}


// stack operations

void push(int n)
{
    //check overflow
    if(top==max-1)
    {
        printf("Overflow !");
        return;
    }
    else
    {
        top++;
        stack[top]=n;
    }
}

int pop()
{
    //check underflow
    int x=0;
    if(top==-1)
    {
        printf("Underflow !\n");
        return 0;
    }
    else
    {
        x=stack[top];
        top--;
        return x;
    }
}
 

---

Also , we can reverse linked list by changing the links .
 In this case too, we have two choices 

• Iterative method
• Recursive method    

What our goal is :

• Set head to last node
• Set link part of former head to NULL
• Set linked parts of all elements to its predecessor 

 Try to implement by taking this in account or check the following implementation !

Reversing a linked list by Changing links :

---

//reversing a singly linked list

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

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

struct node *head=NULL;

void append();
void addatbeg();
void revIt();
void revRe(struct node *);
void display();

int main()
{
int choice;
while(1){
    printf("Enter your choice:\n");
    printf("1.Append\n2.Add at begining\n3.Display\n4.Reverse(Iteration)\n5.Reverse(recurssion)\n6.Exit\n");
    scanf("%d",&choice);

        switch(choice)
        {
            case 1:
                append();break;
            case 2:
                addatbeg();break;
            case 3:
                display();break;
            case 4:
                revIt();break;
            case 5:
                revRe(head);
                display();break;
            case 6:
                return 0;
            default :
                printf("Try valid input\n");
        }
    }
}

void append()
{
    struct node *temp,*trav;
    trav=head;
    temp=(struct node *)malloc(sizeof(struct node));
    int n;
    printf("Enter data to add at end : ");
    scanf("%d",&n);
    temp->data = n;
   
    if(head==NULL)
    {
        temp->link=NULL;
        head=temp;  
    }
    else
    {
        while(trav->link!=NULL)
        {
            trav=trav->link;
        }
        trav->link = temp;
        temp->link = NULL;
    }
   
}


void addatbeg()
{
    struct node *temp;
    temp=head;
    temp=(struct node *)malloc(sizeof(struct node));
    int n;
    printf("Enter data to add at beginning : ");
    scanf("%d",&n);
    temp->data = n;
   
    if(head==NULL)
    {
        temp->link=NULL;
        head=temp;  
    }
   
    else{
        temp->link = head;
        head = temp;
    }
}

void revIt()
{
    struct node *current,*next,*prev;
    current = head;
    prev = NULL;
    while(current != NULL)
    {
        next = current->link;
        current->link = prev;
        prev = current ;
        current = next ;
    }
    head = prev;
    printf("Reversed linked list :\n");
    display();
}
void revRe(struct node *temp)
{

    if(temp->link==NULL)
    {
        head = temp;
        return ;
    }
    revRe(temp->link);
    struct node *temp2;
    temp2 = temp->link;
    temp2->link = temp;
    temp->link = NULL;
   
}

void display()
{
    struct node *temp ;
    temp =head;
    printf("List : ");
    while(temp != NULL)
    {
        printf(" %d ",temp->data);
        temp=temp->link;
    }
}

---

Thanking you !