挑战：
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.
我将把我的代码放在下面，但简单地说，我的解决方案：
- 为原始数组中的每个列表创建一个包含一个节点的排序双链表，其中每个节点都包含头节点的值和该节点所在的数组索引
- 在双链表的头节点指示的索引处弹出单链表的头节点，并将其附加到结果列表的尾部
- 删除双链接列表的标题，并插入一个新节点，表示刚刚弹出的列表的新标题
- 继续，直到双链接列表为空
我认为这实际上不是一种非常有效的方法。在最坏的情况下，将节点插入到双链表中是O(k(。每次从一个单链列表中弹出一个节点时，我都会在列表中插入一个新节点，所以如果n是每个单链列表的平均长度，这不会使我的总体时间复杂性为O(k*(k*n((=O(nk^2(吗？如果是这样的话，我想知道我怎么没有超过这些限制的时间限制：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
无论如何，这是我的(Typescript(代码，包含运行所需的所有驱动程序功能：
// 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
}
至少有两个"计算机科学"；方法：
-
使用堆而不是双链接列表，这允许您弹出(并重新插入1(其头部节点中值最小的列表。
1如果堆实现提供了替换(交换(方法，则使用该方法而不是单独的弹出和推送操作 -
成对合并列表，这样列表的数量就会减少(而它们的大小会增加(，直到只剩下一个列表。为了提高效率，这应该通过分治算法(递归(来完成，每次通过将列表数组一分为二来解决合并问题，直到只剩下一个列表作为基本情况。然后，在回溯的同时，对递归返回的两个列表执行合并。
我将在可运行的JavaScript片段中演示第二个解决方案：
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));这比具有双链表的解决方案具有更好的时间复杂性：它是O(nklogk(而不是O(nk²(。
需要注意的是，当您将所有内容转换为数组并对其进行排序时，JavaScript的速度相当快。但这类练习旨在以最少的空间使用来解决(不包括需要创建或打印列表的部分(
堆版本和非递归成对合并版本的Javascript代码示例，使用小数组(小数组版本更快(。使用C++中的相同代码，1024个列表，每个列表有16384个节点，在我的系统上，堆版本需要3.6秒，而数组版本的速度是1.8秒的两倍。
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
var k = lists.length;
heap(lists); // convert to min heap
const head = lists[0]; // merged list = list[0]
var tail = head;
while (true) {
lists[0] = lists[0].next; // lists[0] = next node
if (lists[0] == null) { // if end of lists[0]
if(--k == 0) // reduce heap size
break;
lists[0] = lists[k]; // lists[0] = last list
}
sift(lists, 0, k); // fix heap
tail = tail.next = lists[0]; // append node to merged list
}
return head;
}
function heap(lists) { // convert lists to min 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]];
}
}
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;
}
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));
非递归成对合并版本，使用小数组ar[]而不是堆栈，其中ar[i]==null或ar[i]=2^i个合并列表(ar[0]用于保存单个列表(。也可以对列表数组使用自下而上的合并排序方法，但初始版本需要第二个大小为K的数组，而在该版本中，第二个数组大小为ceil(log2(K+1((。
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
function mergeKLists(lists) {
if (lists.length < 2) return lists[0];
const sz = Math.ceil(Math.log2(lists.length+1));
const ar = new Array(sz).fill(null);
var mg = null;
var i, j;
for (j = 0; j < lists.length; j++) {
// merge lists[j] into ar[]
mg = lists[j];
for (i = 0; ar[i] != null; i++) {
mg = merge(ar[i], mg);
ar[i] = null;
}
ar[i] = mg;
}
// merge ar[] into single list
for (i = 0; ar[i] == null; i++);
mg = ar[i];
for (++i ; i < sz; i++)
if (ar[i] != null)
mg = merge(ar[i], mg);
return mg;
}
function merge(l0, l1) {
var pair = [l0, l1];
var head = popLeast(pair);
var tail = head;
while (pair[0] && pair[1])
tail = tail.next = popLeast(pair);
tail.next = pair[0] ?? pair[1];
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;
}
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;
}
const lists = [
[1, 4, 5],
[1, 3, 4],
[2, 6],
].map(createList);
const result = mergeKLists(lists);
console.log(stringify(result));