Given an array of k sorted linked lists, your task is to merge them into a single sorted list.

1-merge-k-sorted-lists.js

function mergeTwoLists(list1, list2) {
  let a = list1.head;
  let b = list2.head;

  let ll = null;
  let tail = null;

  while (a !== null || b !== null) {
    let nextNode = null;

    if (a !== null && b !== null) {
      if (a.data <= b.data) {
        nextNode = a;
        a = a.next;
      } else {
        nextNode = b;
        b = b.next;
      }
    } else {
      if (b === null && a !== null) {
        nextNode = a;
        a = a.next;
      } else if (a === null && b !== null) {
        nextNode = b;
        b = b.next;
      }
    }

    if (tail === null) {
      ll = new LinkedList();
      ll.createLinkedList([nextNode.data]);
      tail = ll.head;
    } else {
      tail.next = new LinkedListNode(nextNode.data);
      tail = tail.next;
    }
  }

  return ll;
}

export function mergeKLists(lists) {
  if (lists.length === 0) {
    return;
  }

  let step = 1;

  while (step < lists.length) {
    for (let i = 0; i < lists.length - step; i = i + step * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + step]);
    }
    step *= 2;
  }

  return lists[0].head;
}

2-README.md

Divide-and-conquer algo, merge list in pairs, then again, until only one list is left.