Q. Reverse the group of k nodes in a link list

INPUT:  1->2>3->4->5->6->7->8     K=2

Then

OUTPUT:  1->0->3->2->5->4->7->6->8

METHOD  1

In  this  method we  are  maintaining  an  array  of  size  k  and  then  putting  first  value  at  index  k  and  second  at  k-1  and  so  on........

Then  we  are  putting  value  back  at  link  list..

Here  is  the  working  code  of  it  using  array.

http://ideone.com/pfo26l

Time  Complexity=  O(n)
Space  Complexity=O(k)

METHOD  2

 It  is  a  really  tricky  method  for  coding.  It  is  asked  to  code  many  times  in  interviews.  But  neglecting  this  question  is  not  a  good  option .One  must  practice  this  one  before.

Inplace  method  of  doing  this  question  and  link - link  swap  for  reversing..

http://ideone.com/oLMHyQ

Let  us  see  the  main  code  of  this.....

node* reverse(node* start,int k)
{

node *curr=start,*prev,*next,*end;
int i=0;
prev=end;
end=start;
if(curr==NULL)
return NULL;

while(i<k &&  curr!=NULL)

{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
i++;
}
end->next=reverse(curr,k);
return prev;
}