#include<stdio.h>
#include<stdlib.h>
struct node {
int value;
struct node* next;
};
struct node* createnode(int no) {
struct node*temp;
temp = (struct node*)malloc(sizeof(struct node*));
temp->value = no;
temp->next = NULL;
return temp;
}
struct node * insert(struct node* head, int no) {
struct node *temp, *headcp;
temp = createnode( no);
if(head == NULL)
return temp;
headcp = head;
while(head->next != NULL) {
head = head->next;
}
head->next = temp;
return headcp;
}
void print (struct node* head) {
while(head != NULL) {
printf("%d -> ",head->value);
head = head->next;
}
}
struct node*reverse(struct node*head,int k)
{
int counter=0;
struct node*current,*prev,*nxt;
if(head==NULL || head->next==NULL)
return head;
prev=NULL;
current=head;
nxt=head->next;
while(current && counter!=k)
{
current->next=prev;
prev=current;
current=nxt;
if(nxt)
nxt=nxt->next;
counter++;
}
return prev;
}
struct node*reverseInBlocksIterative(struct node*head,int k)
{
struct node*ret,*newhead,*prev,*current,*last;
int counter=0,i;
if(k==1 || !head || !(head->next))
return head;
for(i=0,ret=head;i<k-1 && ret;i++)
ret=ret->next;
if(!ret)
return reverse(head,k);
current=head;
prev=head;
last=NULL;
while(current)
{
for(i=0;i<k && current;i++)
current=current->next;
newhead=reverse(prev,k);
prev=current;
if(last)
last->next=newhead;
while(newhead->next)
newhead=newhead->next;
last=newhead;
}
return ret;
}
struct node*reverseInBlocksRecursive(struct node*head,int k)
{
int i;
struct node*current,*ptr,*ret;
if(!head)
return NULL;
for(i=0,current=head;i<k && current;i++)
current=current->next;
ret=reverse(head,k);
for(ptr=ret;ptr->next;ptr=ptr->next);
ptr->next=reverseInBlocksRecursive(current,k);
return ret;
}
int main () {
struct node*head=NULL;
head = insert(head, 1);
head = insert(head, 2);
head = insert(head, 3);
head = insert(head, 4);
head = insert(head, 5);
head = insert(head, 6);
head = insert(head, 7);
head = insert(head, 8);
head = insert(head, 9);
head = insert(head, 10);
head = insert(head, 11);
head = insert(head, 12);
int k;
scanf("%d",&k);
head = reverseInBlocksRecursive(head, k);
print(head);
return 0;
}
Tuesday, 12 July 2016
Reverse a Linked List in groups of given size
Subscribe to:
Comments (Atom)