Tuesday, April 17, 2012

Swap nodes of a linked list


For e.g:
Input: 1->2->3->4->5->6
Output: 2->1->4->3->6->5


There are 2 ways I could think by which we can solve this. Both methods take O(n) time.
Method 2 however is more elegant.

Method 1:

public static Node swapNodes(Node head)
{ 
  Node c = head;
  Node p = c;
  
  boolean headSet = false;
  
  while(c != null && c.next != null)
  {
   Node n = c.next; 
   c.next = n.next;
   n.next = c;

   if(!headSet)
   {
    head = n;
    headSet = true;
   }
   else
   {
    p.next = n;
    p = c;
   }
   
   c = c.next;
  }
  
  return head;
}

Method 2:

public static Node swapNodes(Node head)
 { 
  Node c = head;
  
  // Create a dummy node before the head node
  Node dummy = new Node();
  dummy.next = head;

  Node p = dummy;
  
  while(c != null && c.next != null)
  {
   Node n = c.next; 
   c.next = n.next;
   n.next = c;

   p.next = n;
   p = c;
   
   c = c.next;
  }
  
  return dummy.next;
 }

No comments:

Post a Comment