The challenge:
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
I'll put my code below, but briefly, my solution:
- Creates a sorted doubly-linked list containing a node for each list in the original array, where each node contains the value of the head node and the array index at which that node exists
- Pops off the head node of the singly-linked list at the index indicated by the head node of the doubly-linked list and attaches it to the tail of the result list
- Removes the head of the doubly-linked list and inserts a new node representing the new head of the list that was just popped
- Continues until the doubly-linked list is empty
I'm thinking this was actually not a very efficient way to do this. In the worst case, inserting a node into the doubly-linked list is O(k). I insert a new node into the list every time a node is popped off one of the singly-linked lists, so if n is the average length of each singly-linked list, wouldn't that make my overall time complexity O(k * (k*n)) = O(nk^2)? If so, I'm wondering how I didn't exceed the time limit with these constraints:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
Anyway here is my (Typescript) code with all the driver functions necessary to run:
// nodes of the singly-linked lists given by the challenge
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
}
// nodes for the doubly-linked list I used to keep track of what order
// in which to pop from the singly-linked lists
class OrderNode {
headVal: number
listIndex: number
next: OrderNode | null
prev: OrderNode | null
constructor(val: number, i: number, next: OrderNode | null, prev: OrderNode | null) {
this.headVal = val
this.listIndex = i
this.next = next === undefined ? null : next
this.prev = prev === undefined ? null : prev
}
}
// typescript bs
function nullFilter<TValue>(value: TValue | null | undefined): value is TValue {
if (value === null || value === undefined) return false
const test: TValue = value
return true
}
// main function
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const filtered = lists.filter(nullFilter)
if (!filtered.length) return null
// create initial doubly-linked list
let order: OrderNode = insert(null, filtered[0], 0)
for (let i = 1; i < filtered.length; i ) {
order = insert(order, filtered[i], i)
}
let remaining: OrderNode | null = order
// set up initial variables for while loop
const firstI = remaining.listIndex
const firstNode = filtered[firstI]
let head: ListNode | null = push(null, firstNode)
let tail: ListNode | null = head
const firstInsert = shiftList(filtered, firstI)
remaining = shiftOrder(remaining)
if (firstInsert) {
remaining = insert(remaining, firstInsert, firstI)
}
// main while loop
while (remaining) {
const i = remaining.listIndex
// get node to push to end of result list
const pushNode = filtered[i]
// shift that node and get the new head
const newHead = shiftList(filtered, i)
// shift the head of the order list
remaining = shiftOrder(remaining)
// if there are nodes left in the popped list, add the new head to the order list
if (newHead) {
remaining = insert(remaining, newHead, i)
}
tail = push(tail, pushNode)
}
return head
}
// push a node to the end of the result list
function push(tail: ListNode | null, node: ListNode): ListNode {
const newNode = new ListNode(node.val, null)
if (tail) {
tail.next = newNode
}
return newNode
}
// insert a new node into the sorted list keeping track of order
function insert(head: OrderNode | null, node: ListNode, i: number): OrderNode {
const newNode = new OrderNode(node.val, i, null, null)
if (!head) {
return newNode
} else {
if (node.val <= head.headVal) {
head.prev = newNode
newNode.next = head
return newNode
} else {
let temp: OrderNode | null = head
let prev: OrderNode | null = null
while (temp) {
if (temp.headVal >= node.val) break
prev = temp
temp = temp.next
}
prev = prev as OrderNode
if (temp) {
prev.next = newNode
newNode.prev = prev
newNode.next = temp
temp.prev = newNode
return head
} else {
prev.next = newNode
newNode.prev = prev
return head
}
}
}
}
// shift the head from the order list
function shiftOrder(head: OrderNode | null): OrderNode | null {
if (head) {
if (head.next) {
const newHead = head.next
newHead.prev = null
return newHead
} else {
return null
}
} else {
return null
}
}
// shift a node from one of the given lists, and return the new head
function shiftList(lists: Array<ListNode | null>, i: number): ListNode | null {
let currentHead = lists[i]
if (currentHead) {
lists[i] = currentHead.next
return lists[i]
} else {
return null
}
}
// driver code
const input: number[][] = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
]
const lists = input.map(array => {
let next = null
for (let i = array.length - 1; i >= 0; i--) {
next = new ListNode(array[i], next)
}
return next
})
let result = mergeKLists(lists)
while (result) {
process.stdout.write(`${result.val} -> `)
result = result.next
}
CodePudding user response：
There are at least two "computer science" ways of doing it:
Use a heap instead of a doubly linked list, which allows you to pop (and re-insert1) the list that has the least value in its head node.
1 If the heap implementation provides a replace (exchange) method, then use that instead of a separate pop & push action.Merge lists pairwise, so the number of lists reduces (while their size increases), until only one list remains. To make this efficient, this should be done by a divide-and-conquer algorithm (recursion), each time solving the merge by splitting the lists array in halves, until there is only one list left as base case. Then -- while backtracking -- perform the merge on the two lists that come back from recursion.
I will here demo the second solution in a runnable JavaScript snippet:
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
// main function
function mergeKLists(lists) {
// Divide and conquer
if (lists.length < 2) return lists[0]; // Base case
const i = lists.length >> 1; // Half
const pair = [mergeKLists(lists.slice(0, i)), mergeKLists(lists.slice(i))];
// Merge pair of non-empty lists:
const head = popLeast(pair);
let tail = head;
while (pair[0] && pair[1]) {
tail = tail.next = popLeast(pair);
}
tail.next = pair[0] ?? pair[1]; // Attach the remainder
return head;
}
function popLeast(pair) {
const i = pair[0].val < pair[1].val ? 0 : 1;
const least = pair[i];
pair[i] = least.next;
return least;
}
// Helper functions for I/O
function stringify(head) {
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return nodes.join(" -> ");
}
function createList(values) {
let head = null;
for (const val of values.reverse()) {
head = new ListNode(val, head);
}
return head;
}
// driver code
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));This has a better time complexity than the solution with the doubly linked list: it is O(nklogk) instead of O(nk²).
It should be mentioned that JavaScript is quite fast when you convert everything to an array and perform a sort on that. But this kind of exercises is intended to be solved with a minimum use of space (excluding the part where you need to create or print the lists)
CodePudding user response：
As noted in trincot's answer, here is a heap version.
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
var k = lists.length;
heap(lists); // convert to heap
const head = lists[0]; // merged list = list[0]
let tail = head;
while (true) {
lists[0] = lists[0].next; // root = next node
if (lists[0] != null) { // if not end of list
sift(lists, 0, k); // update heap
} else { // else
if(--k == 0) // reduce heap size
break;
lists[0] = lists[k]; // root = last list
sift(lists, 0, k); // update heap
}
tail = tail.next = lists[0];// append node to merged list
}
tail.next = null;
return head;
}
function heap(lists) { // convert lists to heap
var i = (lists.length-1)/2;
while (i >= 0) {
sift(lists, i, lists.length);
i--;
}
}
function sift(lists, i, k) { // sift lists[i] down
var m = i;
while (true) {
i = m;
var l = 2*i 1;
var r = 2*i 2;
if(l < k && lists[l].val < lists[i].val)
m = l;
if(r < k && lists[r].val < lists[m].val)
m = r;
if(m == i)
break;
[lists[i], lists[m]] = [lists[m], lists[i]];
}
}
// Helper functions for I/O
function stringify(head) {
const nodes = [];
while (head) {
nodes.push(head.val);
head = head.next;
}
return nodes.join(" -> ");
}
function createList(values) {
let head = null;
for (var val of values.reverse()) {
head = new ListNode(val, head);
}
return head;
}
// driver code
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));