Merge two sorted linked lists

Technology CommunityCategory: JavaScriptMerge two sorted linked lists
VietMX Staff asked 3 years ago
Problem

The goal here is to merge two linked lists that are already sorted into a new sorted array. For example:

L1 = 1 -> 3 -> 10
L2 = 5 -> 6 -> 9
merge(L1, L2) = 1 -> 3 -> 5 -> 6 -> 9 -> 10

Algorithm: 1. Create a new head pointer to an empty linked list. 2. Check the first value of both linked lists. 3. Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node. 4. Continue this process until you reach the end of a linked list.

function Node(data, next) {
  this.data = data;
  this.next = next;
} 

function merge(L1, L2) {
  
  // create new linked list pointer
  var L3 = new Node(null, null);
  var prev = L3;
  
  // while both linked lists are not empty
  while (L1 !== null && L2 !== null) {
    if (L1.data <= L2.data) { 
      prev.next = L1;
      L1 = L1.next;
    } else {
      prev.next = L2;
      L2 = L2.next;
    }
    prev = prev.next;
  }
  
  // once we reach end of a linked list, append the other 
  // list because we know it is already sorted
  if (L1 === null) { prev.next = L2; }
  if (L2 === null) { prev.next = L1; }
  
  // return the sorted linked list
  return L3.next;
  
}

// create first linked list: 1 -> 3 -> 10
var n3 = new Node(10, null);
var n2 = new Node(3, n3);
var n1 = new Node(1, n2);
var L1 = n1; 

// create second linked list: 5 -> 6 -> 9
var n6 = new Node(9, null);
var n5 = new Node(6, n6);
var n4 = new Node(5, n5);
var L2 = n4; 

merge(L1, L2);