Merge two sorted linked lists

Merging two sorted linked lists is a classic computer science problem with practical applications in data management and algorithm design. This post will walk you through the process of efficiently merging two sorted linked lists in JavaScript, providing clear explanations and illustrative code examples.

We’ll assume our linked list nodes have a data property for the value and a next property pointing to the next node in the sequence. An empty list will have a head property set to null.

First, let’s define a simple LinkedListNode class:

class LinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Now, let’s tackle the merging algorithm. The most efficient approach is iterative, building a new sorted list by comparing the heads of the input lists at each step.

function mergeSortedLists(list1, list2) {
  // Handle empty list cases
  if (!list1) return list2;
  if (!list2) return list1;

  let mergedHead;
  let mergedTail;

  // Determine the smaller head to start with
  if (list1.data <= list2.data) {
    mergedHead = list1;
    list1 = list1.next;
  } else {
    mergedHead = list2;
    list2 = list2.next;
  }
  mergedTail = mergedHead;

  // Iterate through the remaining nodes
  while (list1 && list2) {
    if (list1.data <= list2.data) {
      mergedTail.next = list1;
      list1 = list1.next;
    } else {
      mergedTail.next = list2;
      list2 = list2.next;
    }
    mergedTail = mergedTail.next;
  }

  // Append any remaining nodes from list1 or list2
  mergedTail.next = list1 || list2;

  return mergedHead;
}

This function first handles the edge cases where one or both input lists are empty. It then iteratively compares the data values of the current nodes in list1 and list2, adding the smaller node to the mergedTail of the new list. Finally, it appends any remaining nodes from either list1 or list2 that were not fully processed.

Let’s test this function with an example:

// Example usage:
const list1 = new LinkedListNode(1);
list1.next = new LinkedListNode(3);
list1.next.next = new LinkedListNode(5);

const list2 = new LinkedListNode(2);
list2.next = new LinkedListNode(4);
list2.next.next = new LinkedListNode(6);

const mergedList = mergeSortedLists(list1, list2);

// Print the merged list
let current = mergedList;
while (current) {
  console.log(current.data);
  current = current.next;
} // Output: 1, 2, 3, 4, 5, 6

This example demonstrates how to create sample linked lists and use the mergeSortedLists function to merge them. The output shows the correctly sorted merged list. This efficient iterative approach provides a clear and concise solution to the problem of merging two sorted linked lists in JavaScript. Remember to handle edge cases properly for code. This algorithm boasts a time complexity of O(m+n), where ‘m’ and ‘n’ are the lengths of the input lists, making it optimal.