这是我的 leetcode 解决方案的正确时间复杂度：将 k 个排序的链表合并为 1 个排序的列表吗？

Question

挑战：

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
}

Answer 1

至少有两种“计算机科学”方法可以做到这一点：

使用堆而不是双向链表，它允许您弹出（和re-insert¹）具有最少的列表其头节点中的值。

_{¹ 如果堆实现提供替换（交换）方法，则使用该方法代替单独的弹出和推送操作。}
成对合并列表，因此列表的数量减少（同时它们的大小增加），直到只剩下一个列表。为了提高效率，这应该通过 divide-and-conquer 算法（递归）来完成，每次通过将列表数组分成两半来解决合并，直到只剩下一个列表作为基本情况。然后——在回溯的同时——对从递归返回的两个列表执行合并。

我将在此处演示可运行的 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 非常快。但是这类习题的目的是用最少的space来解决（不包括您需要创建或打印列表的部分）

Answer 2

Javascript 堆版本和 non-recursive 成对合并版本的代码示例，使用小数组（小数组版本更快）。在 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));

Non-recursive 成对合并版本，使用小数组 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));

这是我的 leetcode 解决方案的正确时间复杂度：将 k 个排序的链表合并为 1 个排序的列表吗？

Is this the correct time complexity of my leetcode solution: merge k sorted linked lists into 1 sorted list?

sorting

algorithm

linked-list

time-complexity

typescript