Thursday, April 12, 2012

Reversing Alt grp of K nodes(Iter and Rex)


 public static LinkedList reverseAltK_Iter(LinkedList p, int k){
  LinkedList headNode = null,head = null;
  LinkedList curr = p;
  int count;
  
  while(curr != null ) {
   LinkedList prev = null,next=null;
   LinkedList currHead = curr;
   count = 0;
   while(curr!=null && count < k) {
    next = curr.next;
    curr.next = prev;
    prev=curr;
    curr = next;
    count++;
   }
   if(headNode == null)
    headNode = prev;
   else
      head.next = prev;
   currHead.next = curr;
   count = 0;
   while(curr !=null && count++ < k) {
    prev = curr;
    next = curr.next;
    curr = next;
    currHead = prev;
    //System.out.println(prev.data);
   }
   head = currHead;
   //System.out.println(head.data);
  }
  
  return headNode;
  }
 

 
 public static LinkedList reverseAltK(LinkedList head, int k){
  LinkedList prev = null,next=null;
  LinkedList curr = head;
  int count = 0;
  if(head == null || head.next == null)
   return head;
  
  // Reversing
  while (curr !=null && count < k) {
   next = curr.next;
   curr.next = prev;
   prev = curr;
   curr = next;
   count++;
  }
  
  
  // The next set of k nodes shd not be altered.
  if(head!=null)
   head.next = curr; // jus chg to point to next node
  count = 0;
  while(curr!=null && count < k-1){ // next set of 3 nodes as it is
   curr = curr.next;
   count++;
  }

  if(curr!=null)   // Next set of 3 nodes to be swapped and append the list to curr Node;
   curr.next = reverseK(curr.next,k);
  return prev;
  }

No comments:

Post a Comment