#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:
Post Comments (Atom)
No comments:
Post a Comment