Question: k-reverse of linklist where k>0. This means that you should reverse block of k nodes in a list.


Example:
i/p: 1 2 3 4 5 6 7 8 9 10
o/p:

For k=2: 2 1 4 3 6 5 8 7 10 9
For k=3: 3 2 1 6 5 4 9 8 7 10
For k=4: 4 3 2 1 8 7 6 5 9 10

Algorithm:
This is nothing but an extension of swapping nodes in a linklist. But in my opinion, it's a slightly easier problem than that. One can also use this solution for swapping nodes in a list.

1) check if remaining list has k nodes.
if yes get the pointer of (k+1)th node.
else return.
2) reverse first k nodes.
3) set next of last node (after reversal) to (k+1)th node.
4) move to (k+1)th node.
5) Go to step 1.

Code:

 
struct list* GetNthNode(int n, struct list* head)
{
   if(!head)
       return head;

   struct list* Nth;
   int i;
  
   //Notice the loop body (empty)
   for (i=0, Nth=head; Nth && (i < nth="Nth-">next);

   if(i==n && Nth!=NULL)
       return Nth;
   return head->next;
}

bool isNnodes(struct list* head, int n)
{
   int i;
  
   //Notice the loop body (empty)
   for (i=0 ; head && (i < head="head-">next);
  
   if(i == n)
       return true;
   return false;
}

void reverseN(struct list** list1, int n)
{
   if (n==0 || n==1)
       return;
  
   struct list *cur, *tmp, *next;
   int i;
   cur = *list1;

   if(!isNnodes(*list1,n))
       return;

   *list1 = GetNthNode(n-1,*list1);

   while(cur && isNnodes(cur, n))
   {
       //take care on below step
       tmp = GetNthNode(n, GetNthNode(n-1, cur));
       i=0;

       while(inext;
           cur->next=tmp;
           tmp = cur;
           cur = next;
           i++;
       }
   }
}

PS: Later, I noticed that code can be much shorter than given above and I am leaving that exercise to the readers.

Important: As said many times; it's always better to design a generalized algorithm rather than designing one for a specific case. Since this problem is solving that swap nodes problem, it's beter to design this kind of algorithm so that if in near future some needs arise, you can reuse the code.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.