Tuesday 12 July 2016

Reverse a Linked List in groups of given size



#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;
}