Good morning! Here's our prompt for today.
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
and1000000000
- Let
n
andk
be the length of a linked list and number of lists - Expected time complexity :
O(n*k*log k)
- Expected space complexity :
O(k)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
133
'PASSED: Expect `mergeLists(2 -> 6 -> 9, 1 -> 2 -> 7, 2 -> 6 -> 10)` to return 1 -> 2 -> 2 -> 2 -> 6 -> 6 -> 7 -> 9 -> 10'
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) {
this.tail = newNode;
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Tired of reading? Watch this video explanation!
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...
How do I use this guide?