Merge two sorted linked list

Learn how to merge two sorted linked list.

We will be given two or more sorted linked list and we have to return a single list which is merged in the sorted order.

For example

Input
1 -> 3 -> 5
0 -> 2 -> 4 -> 6

Output:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

We will see two different approaches to implement this algorithm.

Iterative approach to merge the sorted linked list.

We will create a helper function which will carry out the iterative operation of the merging the two lists. It will check each element of both the lists and merge them according to their wattage or value.

If there is an extra element in any of the two nodes than its peer then it will add them at the end of the list.

But to start the merging we will have to first check which list contains the smallest element so that we can start the merging from it. For this, we will create another which will trigger the merging by checking this feature.

//Helper function which will trigger merging
const merge = (node1, node2) => { 
  if (node1 == null) 
    return node2; 
  if (node2 == null) 
    return node2; 

  // start with the linked list 
  // whose head data is the least 
  if (node1.element < node2.element) 
    return mergeUtil(node1, node2); 
  else
    return mergeUtil(node2, node1); 
};

Now to iteratively merge list we will use this function.

const mergeUtil = (node1, node2) => {
  //if first node has only one element
  //then point the second node as next and return it
  if(node1.next === null){
    node1.next = node2;
    return node1;
  }
  
  let curr1 = node1, next1 = node1.next;
  let curr2 = node2, next2 = node2.next;
  
  while (next1 != null && curr2 != null) { 
    // if curr2 lies in between curr1 and next1 
    // then do curr1->curr2->next1 
    if ((curr2.element) >= (curr1.element) && (curr2.element) <= (next1.element)) { 
      next2 = curr2.next; 
      curr1.next = curr2; 
      curr2.next = next1; 

      // now let curr1 and curr2 to point 
      // to their immediate next pointers 
      curr1 = curr2; 
      curr2 = next2; 
    } 
    else { 
      // if more nodes in first list 
      if (next1.next != null) { 
        next1 = next1.next; 
        curr1 = curr1.next; 
      } 

      // else point the last node of first list 
      // to the remaining nodes of second list 
      else { 
        next1.next = curr2; 
        return node1; 
      } 
    } 
  } 
  
  return node1;
}

The following will be the output if we create and execute merging of two lists.

Input:
let node1 = new LinkedList();
let node2 = new LinkedList();

node1.append(1);
node1.append(3);
node1.append(5);

node2.append(0);
node2.append(2);
node2.append(4);
node2.append(6);

let mergedNode = merge(node1.getHead(), node2.getHead());

while(mergedNode){
  console.log(mergedNode.element);
  mergedNode = mergedNode.next;
}

Output:
0
1
2
3
4
5
6

Time complexity: O(m + n).
Space complexity: O(m + n).

---

Recursive approach to merge list.

In this approach we will create a single function which will call itself recursively two merge the list.

In each call, it will check the element of both the lists and merge them according to whose head data is the least.

const mergeRecursive = (node1, node2) => {
    if(node1 === null){
      return node2;
    }

    if(node2 === null){
      return node1;
    }

    // start with the linked list 
    // whose head data is the least 
    if (node1.element < node2.element) { 
      node1.next = mergeRecursive(node1.next, node2); 
      return node1; 
    } 
    else { 
      node2.next = mergeRecursive(node1, node2.next); 
      return node2; 
    } 
};

Input:
let node1 = new LinkedList();
let node2 = new LinkedList();

node1.append(1);
node1.append(3);
node1.append(5);

node2.append(0);
node2.append(2);
node2.append(4);
node2.append(6);

let mergedNode = mergeRecursive(node1.getHead(), node2.getHead());

while(mergedNode){
  console.log(mergedNode.element);
  mergedNode = mergedNode.next;
}

Output:
0
1
2
3
4
5
6

Time complexity: O(n + m).
Space complexity: O(n + m).