Merge two sorted linked lists
Tags: solution, datastructures, algorithms, programming
Published: 2022-05-07 17:34:03

Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return the head of the merged list.

> **Input**: Two lists of N and M nodes are provided
However, number of nodes are not the game changing factor, one can execute the operation even despite measuring the length.

### Approach
Both the lists are sorted, it's a good idea to check either of the 1st node in the list which of them is smaller, consider that advance the pointer corresponding to the smaller node.

An example demonstrated in the following image:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2nsyhf45al1r6dr5z85n.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/krkwt7ih2pd7f4t4nezn.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vgutd6atruu6kj8gs95n.png)


In the end, when there is a left out nodes, we simply just append the nodes to the result list.

For the above approach,
Time Complexity: O(min(n, m))
i.e., The Smallest linked list travel amount.
Space Complexity: O(1)
i.e., No such extra auxiliary space required proportional to input.

Few implementations for the same can be found below.

### 1. Java implementation.
```
/*
  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(int d) {data = d; next = null; }
    }
*/

class LinkedList
{
    Node sortedMerge(Node head1, Node head2) {
     Node res = new Node(-1);
     Node itr = res;
     while(head1 != null && head2 != null) {
         if(head1.data <= head2.data) {
            itr.next = head1;
            head1 = head1.next;
         } else {
            itr.next = head2;
            head2 = head2.next;
         }
         itr = itr.next;
     }
     fillRest(head1, itr);
     fillRest(head2, itr);
     return res.next;
   } 
   
   void fillRest(Node head, Node itr) {
        if(head != null) 
            itr.next = head;
   }
}

```

### 2. JavaScript / Node.js implementation.
```

class Solution {
    fillRest(head, itr) {
        if(head !== null) 
            itr.next = head;
   }
   
    sortedMerge(head1, head2)
    {
        let res = new Node(-1);
        let itr = res;
        
        let getMin = () => {
            let min;
            if(head1.data <= head2.data) {
                min = head1;
                head1 = head1.next;
            } else {
                min = head2;
                head2 = head2.next;
            }
            return min;
        };
        
        while(head1 !== null && head2 !== null) {
             itr.next = getMin();
             itr = itr.next;
        }
         this.fillRest(head1, itr);
         this.fillRest(head2, itr);
         return res.next;
    }
}

```

### 3. C++ implementation.

```

/* Link list Node
struct Node {
  int data;
  struct Node *next;
  
  Node(int x) {
    data = x;
    next = NULL;
  }
};
*/


//Function to merge two sorted linked list.
Node* sortedMerge(Node* head1, Node* head2)  
{  
    // code here
    Node res(-1);
     Node *itr = &res;
     
     auto fillRest = [] (Node* head, Node* itr) {
            if(head != NULL) 
                itr->next = head;
        };
     
     
     while(head1 != NULL && head2 != NULL) {
         if(head1 -> data <= head2 -> data) {
             itr-> next = head1;
             head1 = head1 -> next;
         } else {
             itr-> next = head2;
             head2 = head2 -> next;
         }
         itr = itr -> next;
     }
     
     fillRest(head1, itr);
     fillRest(head2, itr);
     return res.next;
}  

```