Created
August 28, 2012 05:41
-
-
Save murikadan/3495254 to your computer and use it in GitHub Desktop.
To reverse K nodes in a linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
4 | |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
struct node | |
{ | |
int val; | |
struct node* next; | |
}; | |
void enqueue(struct node**,struct node **,struct node **); | |
struct node* dequeue(struct node**,struct node **); | |
void traverse(struct node*); | |
void push(struct node**,struct node**); | |
struct node* pop(struct node**); | |
void listrev(struct node**,struct node**,int); | |
void free_queue(struct node*); | |
int isstackempty(struct node*); | |
struct node* makenode(int); | |
int listlength(struct node*); | |
struct node* filndlast(struct node*); | |
int main() | |
{ | |
int key,k; | |
struct node *front=NULL,*rear=NULL; | |
FILE *fp; | |
fp=fopen("input","r"); | |
fscanf(fp,"%d",&k); | |
fscanf(fp,"%d",&key); | |
while(!feof(fp)) | |
{ | |
struct node* newnode=makenode(key); | |
enqueue(&front,&rear,&newnode); | |
fscanf(fp,"%d",&key); | |
} | |
fclose(fp); | |
fp=fopen("output","w"); | |
fclose(fp); | |
traverse(front); | |
listrev(&front,&rear,k); | |
traverse(front); | |
free_queue(front); | |
return 0; | |
} | |
void enqueue(struct node** front,struct node** rear,struct node** newnode) | |
{ | |
(*newnode)->next=NULL; | |
if(*front==NULL) | |
*front=*rear=*newnode; | |
else | |
{ | |
(*rear)->next=*newnode; | |
(*rear)=*newnode; | |
} | |
} | |
struct node* 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; | |
return temp; | |
} | |
void free_queue(struct node* front) | |
{ | |
while(front!=NULL) | |
{ | |
struct node* save=front->next; | |
free(front); | |
front=save; | |
} | |
} | |
void traverse(struct node* head) | |
{ | |
struct node* temp=head; | |
while(temp!=NULL) | |
{ | |
printf("%d",temp->val); | |
if(temp->next!=NULL) | |
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; | |
} | |
struct node* makenode(int key) | |
{ | |
struct node* newnode=malloc(sizeof(struct node)); | |
newnode->val=key; | |
newnode->next=NULL; | |
return newnode; | |
} | |
int listlength(struct node* head) | |
{ | |
int count=0; | |
struct node* temp=head; | |
while(temp!=NULL) | |
{ | |
count++; | |
temp=temp->next; | |
} | |
return count; | |
} | |
struct node* findlast(struct node* head) | |
{ | |
if(head!=NULL) | |
while(head->next!=NULL) | |
head=head->next; | |
return head; | |
} | |
void listrev(struct node** front,struct node** rear,int k) | |
{ | |
struct node *temp1=NULL,*temp2=NULL,*top=NULL,*head=NULL,*save=NULL; | |
int i=0,flag=0; | |
temp1=head=*front; | |
*front=*rear=NULL; | |
save=temp1; | |
int len=listlength(head); | |
int times=len/k; | |
while(times--) | |
{ | |
temp1=head; | |
while(temp1!=NULL&&i++<k) | |
{ | |
temp2=temp1->next; | |
push(&top,&temp1); | |
temp1=temp2; | |
} | |
head=temp1; | |
if(!isstackempty(top)) | |
temp1=pop(&top); | |
if(flag>0) | |
save->next=temp1; | |
if(flag==0) | |
*front=temp1; | |
while(!isstackempty(top)) | |
{ | |
temp2=pop(&top); | |
temp1->next=temp2; | |
temp1=temp2; | |
} | |
save=temp1; | |
i=0; | |
flag++; | |
} | |
if(head!=NULL) | |
save->next=head; | |
else | |
save->next=NULL; | |
*rear=findlast(*front); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Reverse linked list by k nodes each
for eg
for k=4
input
4
list:1---->2---->3---->4---->5---->6---->7---->8---->9
o/p:4---->3---->2---->1---->8---->7---->6---->5---->9
No additional space required, no new nodes are created, uses a stack for reversal