Problem
Given k linked lists where each one is sorted in the ascending order, merge all of them into a single sorted linked list.
Example
{
"lists": [
[1, 3, 5],
[3, 4],
[7]
]
}
Output:
[1, 3, 3, 4, 5, 7]
Solution
function merge(l1, l2) {
const LinkedListNode = class {
constructor(value) {
this.value = value;
this.next = null;
}
};
let dummy = new LinkedListNode(0);
let tail = dummy;
while (l1 != null && l2 != null) {
if (l1.value < l2.value) {
tail.next = l1;
l1 = l1.next;
}
else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
if (l1 != null) {
tail.next = l1;
}
if (l2 != null) {
tail.next = l2;
}
return dummy.next;
}
function merge_k_lists(lists) {
if (lists.length === 0) {
return null;
}
while (lists.length > 1) {
let mergedLists = [];
let a = lists.shift();
let b = lists.shift();
mergedLists = merge(a, b);
lists.push(mergedLists);
}
return lists[0];
}
const lists = [
[1, 3, 5],
[3, 4],
[7]
];
const result = merge_k_lists(lists);
console.log(result);
Tech Corner 