AlgoDaily - Merge K (Multiple) Sorted Lists

Merge K (Multiple) Sorted Lists (Hard)

Good evening! Here's our prompt for today.

You may see this problem at Coursera, Quora, Robinhood, Datadog, Zapier, Carta, Veeam, Tradeshift, Anaplan, and Qualtrics.

You're given an array of multiple sorted linked lists. Can you write a method that returns it transformed into a single sorted linked list?

Each linked list can be represented as a series of nodes with the following definition:

JAVASCRIPT

1function Node(val) {
2  this.value = val;
3  this.next = null;
4}

Here's how it would be invoked:

JAVASCRIPT

1// Input
2const arr = [
3  2 -> 6 -> 9,
4  1 -> 2 -> 7,
5  2 -> 6 -> 10
6]
7
8mergeLists(arr);
9
10// Output
111 -> 2 -> 2 -> 2 -> 6 -> 6 -> 7 -> 9 -> 10

Constraints

Each list can have up to 100000 nodes
The cumulative sum of all the nodes in the linked lists will be <= 100000
The values in the nodes will be in the range -1000000000 and 1000000000
Let n and k be the length of a linked list and number of lists
Expected time complexity : O(n*k*log k)
Expected space complexity : O(k)

xxxxxxxxxx
​
 
var assert = require('assert');
​
function mergeLists(arrOfLists) {
  // fill in this method
  return [];
}
​
// Supporting data structures
​
function Node(val) {
  this.val = val;
  this.next = null;
}
​
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
​
  prepend(newVal) {
    const currentHead = this.head;
    const newNode = new Node(newVal);
    newNode.next = currentHead;
    this.head = newNode;
​
    if (!this.tail) {

OUTPUT

Results will appear here.