Skip to content

Instantly share code, notes, and snippets.

@murikadan
Created August 26, 2012 12:43
Show Gist options
  • Save murikadan/3478676 to your computer and use it in GitHub Desktop.
Save murikadan/3478676 to your computer and use it in GitHub Desktop.
Program to reverse a linked list using stack
#include <stdio.h>
#include <stdlib.h>
struct node
{
int val;
struct node* next;
};
void enqueue(struct node**,struct node **,int);
void dequeue(struct node**,struct node **);
void traverse(struct node*,struct node*);
void push(struct node**,struct node**);
struct node* pop(struct node**);
void listrev(struct node**,struct node**);
void free_queue(struct node*);
void free_stack(struct node*);
int isstackempty(struct node*);
int main()
{
int key;
struct node *front=NULL,*rear=NULL;
FILE *fp;
fp=fopen("input","r");
fscanf(fp,"%d",&key);
while(!feof(fp))
{
enqueue(&front,&rear,key);
fscanf(fp,"%d",&key);
}
traverse(front,rear);
listrev(&front,&rear);
traverse(front,rear);
free_queue(front);
return 0;
}
void enqueue(struct node** front,struct node** rear,int num)
{
struct node* newnode=malloc(sizeof(struct node));
newnode->val=num;
newnode->next=NULL;
if(*front==NULL)
*front=*rear=newnode;
else
{
(*rear)->next=newnode;
(*rear)=newnode;
}
}
void dequeue(struct node** front,struct node** rear)
{
struct node* temp=NULL;
if(*front==*rear)
{
temp=*front;
*front=*rear=NULL;
}
else if(*front!=NULL)
{
temp=*front;
*front=(*front)->next;
}
if(temp!=NULL)
{
temp->next=NULL;
free(temp);
}
}
void free_queue(struct node* front)
{
while(front!=NULL)
{
free(front);
front=front->next;
}
}
void traverse(struct node* front,struct node* rear)
{
struct node* temp=front;
while(temp!=NULL)
{
printf("%d",temp->val);
if(temp!=rear)
printf("--->");
else
printf("\n");
temp=temp->next;
}
}
void push(struct node** top,struct node** newnode)
{
(*newnode)->next=NULL;
if(*top==NULL)
*top=*newnode;
else
{
(*newnode)->next=*top;
*top=*newnode;
}
}
struct node* pop(struct node** top)
{
struct node* temp=NULL;
if(!isstackempty(*top))
{
temp=(*top);
*top=(*top)->next;
}
temp->next=NULL;
return temp;
}
int isstackempty(struct node* top)
{
if(top==NULL)
return 1;
else
return 0;
}
void listrev(struct node** front,struct node** rear)
{
struct node *temp1=NULL,*temp2=NULL,*top=NULL;
temp1=*front;
while(temp1!=NULL)
{
temp2=temp1->next;
push(&top,&temp1);
temp1=temp2;
}
if(!isstackempty(top))
*front=pop(&top);
temp1=*front;
while(!isstackempty(top))
{
temp2=pop(&top);
temp1->next=temp2;
temp1=temp2;
}
*rear=temp1;
}
/*
Linked list is read from a file called input
Content of the file is integers
*/
@19mayank19
Copy link

itna bda!!!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment