This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Sunday, 14 June 2015

Reverse a Linked List in groups of given size


package linkedlist.singly;

/*
Reverse a Linked List in groups of given size
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs:  10->20->30->40->50->60->70->80->NULL and k = 30 
Output:  30->20->10->60->50->40->80->70->NULL. 

Inputs:   10->20->30->40->50->60->70->80->NULL and k = 50
Output:  50->40->30->20->10->80->70->60->NULL. 
*/
public class ReverseKNodesInList {

 Node startNode=null;
 public static void main(String[] args) {

  ReverseKNodesInList g = new ReverseKNodesInList();
  Node n1 = new Node(10);
  Node n2 = new Node(20);
  Node n3 = new Node(30);
  Node n4 = new Node(40);
  Node n5 = new Node(50);
  Node n6 = new Node(60);
  Node n7 = new Node(70);
  Node n8 = new Node(80);

  g.startNode = n1;

  n1.setNext(n2);
  n2.setNext(n3);
  n3.setNext(n4);
  n4.setNext(n5);
  n5.setNext(n6);
  n6.setNext(n7);
  n7.setNext(n8);

  Node rev = kreverseWay1(g.startNode, 3);
  g.printLinkList(rev);

  //Node rev = kreverseWay2(g.startNode, 7);
  //g.printLinkList(rev);
 }

 private static Node kreverseWay1(Node startNode, int i) {
  Node temp = startNode;

  Node previousStart = startNode;

  Node newStart=null;
  Node newLast=null;

  boolean firstTime = true;
  int count=0;

  while(temp!=null){

   if(count==i-1){
    Node ahead = temp.getNext();
    temp.setNext(null);

    Node reversed = reverseWay1(previousStart);

    if(firstTime){
     newStart = reversed; 
     newLast = previousStart;
     firstTime=false;
    }else{
     newLast.setNext(reversed);
     newLast = previousStart;
    }
   
    temp=ahead;
    count=0;
    previousStart=temp;
   }else{
    temp=temp.getNext();
    count++;
   }
  }

  if(previousStart!=null){
   Node reversed = reverseWay1(previousStart);
   if(newLast!=null){
    newLast.setNext(reversed);
   }else{
    newStart=reversed;
   }
  }

  return newStart;
 }

 private static Node reverseWay1(Node startNode) {
  Node a = null;
  Node b=startNode;
  while(b!=null){
   Node c = b.getNext();
   b.setNext(a);
   a=b;
   b=c;
  }
  return a;
 }

 public static Node kreverseWay2(Node list, int k){
  Node prev = list;
  int i = 0;

  //first block special case?
  while(list != null && i++ < k){
   list = list.getNext();
  }
  Node retval = reverseWay2(prev, k);

  while(list != null){
   i = 0;
   Node me = list;
   while(list != null && i++ < k)
    list = list.getNext();
   Node end = reverseWay2(me, k);
   prev.setNext(end);

   prev = me;
  }
  return retval;
 }

 public static Node reverseWay2(Node list, int k){
  Node prev = null;
  while(list != null && k-- > 0){
   Node next = list.getNext();
   list.setNext(prev);
   prev = list;
   list = next;
  }
  return prev;
 }
 
 private void printLinkList(Node startNode) {
  Node tempNode = startNode;
  while(tempNode!=null){
   System.out.print(tempNode.getData() + " ");
   tempNode = tempNode.getNext();
  }
 }
}



No comments:

Post a Comment