/*
  Merge two linked lists 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/

Node mergeLists(Node headA, Node headB) {
    if(headA == null && headB == null)
        return null;
    
    if(headA == null)
        return headB;
    
    if(headB == null)
        return headA;
    
    Node root = (headA.data < headB.data)? headA: headB;
    
    while(headA != null && headB != null){
        
        if(headA.data < headB.data){
            if((headA.next == null) || (headA.next != null && headB.data < headA.next.data)){
                Node tmp = headB.next;
                headB.next = headA.next;
                headA.next = headB;
                
                headB = tmp;
            }
             headA = headA.next;
        }else {
            if((headB.next == null) || (headB.next != null && headA.data < headB.next.data)){
                Node tmp = headA.next;
                headA.next = headB.next;
                headB.next = headA;
                
                headA = tmp;
            }
            headB = headB.next;
        }
    }
    
    return root;
}