17 Nov 2013

Reverse Alternative Chunks in a Linked List

Problem Statement:
            Reverse Alternative chunks in the Singly Linked List
   Given below is the scenario:

         
Here size of chunk k=3.


Solution:

As can be seen the chunks are: 
1st Chunk : 1->2->3 
2nd Chunk: 4->5->6
3rd Chunk: 7->8

Therefore, only 1st and the 3rd chunks are reversed, hence the resultant singly linked list.

Full Source Code: LINK

public Node reverseAlternativeChunks(Node root, int k , boolean flag){
  
   if(root==null)
    return null;
  
   Node first=root;
   Node current=first;
  
   int count = k-1;
   while(current.next!=null && count > 0)
   {
    current=current.next;
    count--;
   }
  
   Node  last=reverseAlternativeChunks(current.next,k , !flag);
   current.next=null;
    
   Node subHead = null;
   if(flag){
    subHead=reverse(first);
    first.next=last;
   }
   else
   {
    subHead = first;
    current.next=last;
   }
   
   return subHead;
  }


The Iterative solution can be tried by the users.
Problem similar to this problem is here
Please comment and suggest if any improvisation possible. Your critiques are most welcome , feel free to comment.

Happy Coding !! :)


No comments:

Post a Comment