Merge two sorted linked lists in one list

Merge two sorted linked lists

Given two sorted linked list, we need to merge two sorted linked lists into one without creating any additional node i.e in O(1) space complexity. Please read basics of linked lists and insert node in sorted linked list before attempting this problem.

Coming back to merge two sorted linked list, figure shows two sorted linked lists are merged into one linked list.
merge two sorted linked lists

Merge two sorted linked lists : Algorithm

First, figure out which node will be the head of the resulting list. It can be easily found by comparing head nodes of both lists, whichever is smaller is the head of resultant list. Now, there are n-1 nodes in one list (from list from which head node was taken) and m nodes in another. Task is now reduced to merge these two remaining linked lists. Once we merge these two lists, next of head node will point to head of resultant linked list.

Second, at each node figure out which list to advance. Store the smaller node and then point its next to the resultant linked list which is returned by merge two linked list after removing the smaller node.
It can be implemented using recursion, same processing (merging) has to be done on n-1 and m nodes again. Base case for recursion will be when one of the linked list has been completely traversed and reached till NULL. Then we just have to attach all remaining nodes in other linked list in resultant linked list. For example if there are two lists as follows

1->2->5->6-NULL and 3->4->7->NULL

In this case while comparing 1 and 3, head node will be 1 So result = Node 1 This will be head of resultant list after merge linked lists. We are left with following linked lists to be merged.

2->5->6->NULL and 3->4->7->NULL

Now, again 2 and 3 are compared and result will be 3. Now linked lists to be merged are

5->6->NULL and 3->4->7>NULL

At this point 3 and 5 are compared and 3 is stored as result. 
Remaining linked lists are

5->6-> NULL and 4->7->NULL

With same manner when NULL node is encountered,recursion start unwinding and at every function return result which we stored will be returned and the next of previous invocation’s result node.
In the code we are storing a pointer result (node which is smaller when heads are compared), and next of that result node will be returned value of next invocation of merge function.

Merge two sorted linked lists : Implementation


#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(!a)
        return b;
    else if(!b)
        return a;
 
    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = mergeSort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = mergeSort(a,b->next);
      }
      return result;
}
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}
 
 
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;

        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = mergeSort(L1,L2); 
        printList(L1);
 
        return 0;
}

Explanation merge two sorted linked list implementation is shown in figure.

example of merge two linked lists

Above code is used when we recursively try to flatten a linked list as shown in figure below
flatten linked list

void printFlatList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->down;
	}
	printf("Null");
}
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(!a)
        return b;
    else if(!b)
        return a;
 
    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->down = mergeSort(a->down,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->down = mergeSort(a,b->down);
      }
      return result;
}
 
Node * flattenLinkedList(Node *root){
	if(!root || !root->next) return root;
    return mergeSort(root, flattenLinkedList(root->next));
}

Merge two sorted linked list : Test cases

1. Two equal lengths linked list
L1  = 3->6->7->9->NULL
L2 = 1->2->5->8->NULL

2. One list have elements smaller than head of other
L1 = 1->2->3->4->NULL
L2 = 5->6->7->8->NULL

3.One list as NULL
L1 = NULL
L2  = 5->6->7->8->NULL

4. Both lists are NULL
L1 = NULL
L2 = NULL

5. Scale testing
L1 with a million nodes
L2 with million nodes

6. Test case 2 with millions nodes, to see if stack overflows.

7. Linked lists with duplicate elements
L1 = 3->3->4->6->NULL
L2 = 1->1->2->6->8->NULL

Complexity of merge two sorted linked list in one is O(M+N), where M and N are lengths of two linked lists. Recursive implementation of algorithm has inherent space complexity of O(max(M,N)). In production, recursive implementation with space complexity which is dependent on input size is avoided. Iterative solution are better in that case.

Iterative solution to merge two sorted linked lists

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    printf("NULL");
    printf("\n");
}

Node * MergeLists(Node *list1, Node *list2) {
  if (!list1) return list2;
  if (!list2) return list1;
 
  Node *head;
  if (list1->data < list2->data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1->next && list2) {
    if (list1->next->data > list2->data) {
      Node *tmp = list1->next;
      list1->next = list2;
      list2 = tmp;
    }
    list1 = list1->next;
  } 
  if (!list1->next) list1->next = list2;
  return head;
}

int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;

        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = MergeLists(L1,L2); 
        printList(L1);
 
        return 0;
}

This is a typical example of advancing pointers and keeping track of next pointers while traversing linked lists. In this implementation, List 1 (list1) always point to smaller node at after each comparison.
Since it is already know that we have taken one node from List 1, we take next node of List 1 and current node from List 2. Compare them and if next node of List 1 (list->next) is greater than other node (list2), link current node of list 1 with current node of List 2 (list->next = list2). After this step, swap List 1 and List 2 pointer.

Please share your thoughts on implementations or explanation if something can be improved or if something is wrong and sharing is caring! 🙂