Merging two sorted Link lists without making new node.

    
/*
  Merge two sorted lists A and B as one linked list.
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/



Node* MergeLists(Node *headA, Node* headB)
{
    // This method will take two parameters as pointer to head nodes of both link list,
    // and return pointer to head node of merged sorted link list.
    
    Node *prevA,*prevB,*temp;
    prevA=NULL;
    
    // Plan to merge B in A. So, set returning pointer point to the head of A.
    Node * ans=headA;   
    while(headA && headB)
        {
        
        
        // if current node value of A is greater or equal to that of B.
        if(headA->data >= headB->data)
            {
              
                
                // if prevA is not NULL.
                if(prevA)
                   {
                   temp=headB;
                   headB=headB->next;
                   temp->next=headA;
                   prevA->next=temp;
                   prevA=temp;
                }
                
                
                // if prevA is NULL.
                else 
                   {
                     
                    temp=headB;
                    headB=headB->next;
                    temp->next=headA;
                    prevA=temp;
                    ans=temp;
               }
               
        }
        
        
        // if current node value of A is less than that of B.
        else if(headA->data < headB->data)
            {
                       
            prevA=headA;
            headA=headA->next;   
        }
       
        
    }
      
     if(!headA && headB)
        {
         
         // if A is exhausted but B is not. So, link last node of A to head of B.
         if(prevA)
           prevA->next=headB;
         
         
         // if Given A is NULL. So, make returning node point to the head of B.   
         else 
           ans=headB;
         
         }
     
    return ans;
    
}


Time Complexity : O(m+n)
m=length of link list A.
n=length of link list B.
Space Complexity : O(1)