One Pager Cheat Sheet
- You can merge multiple
sorted linked lists
into a single sorted linked list, with time complexity ofO(n*k*log k)
and space complexity ofO(k)
. - We can improve the brute force solution to sorting a list of linked lists by introducing a
Priority Queue
data structure, which allows us to efficiently process and order elements one by one inO(n log n)
time. - The process involves
running
thelinked lists
through the designated software to achieve the desired result. - Always check for an empty array before attempting any operations.
Putting it all together
is the key to achieving success.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
170
}
var assert = require('assert');
​
function mergeLists(arrOfLists) {
if (!arrOfLists || arrOfLists.length === 0) {
return [];
}
​
let pq = new PriorityQueue();
for (let list of arrOfLists) {
if (list) {
let currentNode = list;
pq.insert(currentNode.val);
​
while (currentNode.next) {
pq.insert(currentNode.next.val);
currentNode = currentNode.next;
}
}
}
return pq.first || [];
}
​
// Supporting data structures
​
class PriorityQueue {
constructor() {
this.first = null;
this.size = 0;
}
​
insert(val) {
const newNode = new Node(val);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.