合并 K 个排序链表的算法解决方案 | 逐一两两合并、优先队列、分治法

合并 K 个排序链表是一个经典的算法问题，通常可以通过多种方法来解决。以下是几种常见的解决方案：

1. 逐一两两合并

这种方法是最直观的，但效率较低。具体步骤如下：

• 依次将链表两两合并，直到所有链表合并成一个。

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 !== null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
}

function mergeKLists(lists) {
    if (lists.length === 0) return null;

    let result = lists[0];
    for (let i = 1; i < lists.length; i++) {
        result = mergeTwoLists(result, lists[i]);
    }

    return result;
}

2. 使用优先队列（最小堆）

这种方法效率更高，时间复杂度为 O(N log K)，其中 N 是所有链表中的节点总数，K 是链表的数量。

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(node) {
        this.heap.push(node);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return min;
    }

    bubbleUp(index) {
        const node = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (node.val >= parent.val) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = node;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        const node = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let swapIndex = null;

            if (leftChildIndex < length) {
                if (this.heap[leftChildIndex].val < node.val) {
                    swapIndex = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                if (
                    (swapIndex === null && this.heap[rightChildIndex].val < node.val) ||
                    (swapIndex !== null && this.heap[rightChildIndex].val < this.heap[leftChildIndex].val)
                ) {
                    swapIndex = rightChildIndex;
                }
            }

            if (swapIndex === null) break;
            this.heap[index] = this.heap[swapIndex];
            index = swapIndex;
        }
        this.heap[index] = node;
    }

    isEmpty() {
        return this.heap.length === 0;
    }
}

function mergeKLists(lists) {
    const minHeap = new MinHeap();
    for (let list of lists) {
        if (list) {
            minHeap.push(list);
        }
    }

    const dummy = new ListNode(0);
    let current = dummy;

    while (!minHeap.isEmpty()) {
        const node = minHeap.pop();
        current.next = node;
        current = current.next;
        if (node.next) {
            minHeap.push(node.next);
        }
    }

    return dummy.next;
}

3. 分治法

分治法也是一种高效的解决方案，时间复杂度为 O(N log K)。

function mergeKLists(lists) {
    if (lists.length === 0) return null;
    return merge(lists, 0, lists.length - 1);
}

function merge(lists, left, right) {
    if (left === right) return lists[left];
    const mid = Math.floor((left + right) / 2);
    const l1 = merge(lists, left, mid);
    const l2 = merge(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 !== null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
}

总结

• 逐一两两合并：简单直观，但时间复杂度较高，适合链表数量较少的情况。
• 优先队列（最小堆）：效率较高，适合链表数量较多的情况。
• 分治法：效率高，适合链表数量较多的情况。

根据实际需求选择合适的解决方案。