Wednesday, April 30, 2014

Reverse a linked list from a given location

Suppose you have following list
1->2->3->4->5

if add you are asked to reverse the list from 3 node, then output sequence would be
1->2->5->4->3


 if add you are asked to reverse the list from 2 node, then output sequence would be
1->5->4->3->2

Code


class linkedList{
    private linkedList next;
 private int val;

 public linkedList(int x){
  val = x;
 }

 public void addToList(linkedList n){
  linkedList templinkedList = this;
  while (templinkedList.next != null){
   templinkedList = templinkedList.next;
  }
  templinkedList.next = n;
 }

 public void print(){
  linkedList templinkedList = this;
  while (templinkedList != null){
   System.out.println(templinkedList.val);
   templinkedList = templinkedList.next;
  
  }
 }
 public linkedList reverseA(int x) {
  x =x-1;
  boolean firstNode = true;
  linkedList init = this;
  linkedList root = this;
  linkedList current = root;
  linkedList forward;
  linkedList chainList = null;
  int i = 0;
  while ( current.next!= null){
   if ( i == x){
    i =0;
    if (firstNode == true){
     init = root;
     firstNode = false;
    }
    chainList = current;
    root = current.next;
    current = root;
   
   
   }
  
   i++;
   forward = current.next;
  
   current.next = forward.next;
  
   if (firstNode){
    forward.next = root;
    root = forward;
   }
   else{
    forward.next = chainList.next;
    chainList.next = forward;
   }
  
  }
  if ( x== -1)
   return root;
  return init;
 }
 public void reverseFromMid(linkedList root){
 // linkedList init = root.next;
  linkedList current = root.next;
  linkedList forward = current.next;
 
  while (forward.next != null){
   current.next = forward.next;
   forward.next = root.next;
   root.next = forward;
   forward = current.next;
  }
 
  int tempVal = forward.val;
  forward.val = root.val;
  root.val = tempVal;
 }
}
public class RevListInParts {
 public static void main(String[] args) {
  linkedList n = new linkedList(1);
  linkedList n2 = new linkedList(2);
  linkedList n3 = new linkedList(3);
  linkedList n4 = new linkedList(4);
  linkedList n5 = new linkedList(5);
  linkedList n6 = new linkedList(6);
  linkedList n7 = new linkedList(7);
  linkedList n8 = new linkedList(8);
  n.addToList(n2);
  n.addToList(n3);
  n.addToList(n4);
  n.addToList(n5);
  n.addToList(n6);
  n.addToList(n7);
  n.addToList(n8);
  n.print();
 // n = n.reverse(3);
  n.reverseFromMid(n2);
  System.out.println("Post reverse");
  n.print();
 
 }
}
 

No comments:

Post a Comment