Merge two sorted linked lists

                            Solution in C :

In C++ :

/*
  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 *a, Node*b)
{
  // This is a "method-only" submission. 
  // You only need to complete this method 
    Node* result = NULL;
 
  /* Base cases */
  if (a == NULL) 
     return(b);
  else if (b==NULL) 
     return(a);
 
  /* Pick either a or b, and recur */
  if (a->data <= b->data) 
  {
     result = a;
     result->next = MergeLists(a->next, b);
  }
  else
  {
     result = b;
     result->next = MergeLists(a, b->next);
  }
  return(result);
}



In C :


// Complete the mergeLists function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode* next;
 * };
 *
 */
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedList *newHead = malloc(sizeof(SinglyLinkedList));
    newHead->head = NULL;
    newHead->tail = NULL;
    
    while(head1 != NULL && head2 != NULL){
        if(head1->data > head2->data){
            insert_node_into_singly_linked_list(&newHead, head2->data);
            head2 = head2->next;
        }
        else if(head1->data < head2->data){
            insert_node_into_singly_linked_list(&newHead, head1->data);
            head1 = head1->next;
        }
        else{
            insert_node_into_singly_linked_list(&newHead, head1->data);
            insert_node_into_singly_linked_list(&newHead, head2->data);
            head1 = head1->next;
            head2 = head2->next;
        }
    }
    
    while(head1 != NULL){
        insert_node_into_singly_linked_list(&newHead, head1->data);
        head1 = head1->next;
    }
    while(head2 != NULL){
        insert_node_into_singly_linked_list(&newHead, head2->data);
        head2 = head2->next;
    }
    
    return newHead->head;
}





In Java :



/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/

Node MergeLists(Node list1, Node list2) {
     // This is a "method-only" submission. 
     // You only need to complete this method 
    
    Node dummy = new Node();
    dummy.next=null;
    dummy.data=0;
    
    Node temp= dummy;
    
    while(true)
        {
        
        if(list1==null)
        {    temp.next = list2;
            break;
        }
        else if(list2==null){
            temp.next = list1;
            break;
        }
        else if(list1.data < list2.data)
            {
              
              temp.next=list1;
              list1=list1.next;
            
        }
        
        else{
            temp.next=list2;
            list2=list2.next;
            
        }
        temp=temp.next;
    }
    return dummy.next;
    

}



In python3 : 


"""
 Merge two linked lists
 head could be None as well for empty list
 Node is defined as
 
 class Node(object):
 
   def __init__(self, data=None, next_node=None):
       self.data = data
       self.next = next_node

 return back the head of the linked list in the below method.
"""

def MergeLists(headA, headB):
    if (headA==None) | (headB==None):
        if(headA == None):
            return headB
        else:
            return headA
    if headA.data > headB.data:                  # headA points to the smaller one
        temp = headA
        headA = headB
        headB = temp
    head = headA
    curA = headA.next                         # curA one step ahead
    curB = headB
    while (curA!=None) & (curB!=None):
        if (curA.data>=curB.data):
            headB =headB.next
            curB.next = curA
            headA.next = curB
            headA = curA
            curA = curA.next
            curB = headB
        else:
            headA =curA
            curA = curA.next
    if curA == None:
        headA.next = headB
    return head