合并 K 个有序链表的两种方法：分治法与优先队列 | 算法详解

合并 K 个有序链表是一个经典的算法问题，通常可以通过分治法或优先队列（最小堆）来解决。下面我将详细解释这两种方法，并提供相应的代码实现。

方法一：分治法（Divide and Conquer）

分治法的核心思想是将 K 个链表分成两半，递归地合并每一半，最后将两个合并后的链表再合并成一个。

时间复杂度分析：

• 每次合并两个链表的时间复杂度为 O(n)，其中 n 是两个链表的总长度。
• 分治法的时间复杂度为 O(K log K)，因为每次递归都将问题规模减半。

代码实现（JavaScript）：

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

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

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (l1 && l2) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    current.next = l1 || l2;
    return dummy.next;
}

方法二：优先队列（最小堆）

优先队列（最小堆）的方法是将所有链表的头节点放入最小堆中，每次从堆中取出最小的节点，并将其下一个节点放入堆中，直到堆为空。

时间复杂度分析：

• 每次插入和删除堆的时间复杂度为 O(log K)。
• 总共有 N 个节点，因此总时间复杂度为 O(N log K)。

代码实现（JavaScript）：

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 node = this.heap[index];
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let swapIndex = null;
            if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].val < node.val) {
                swapIndex = leftChildIndex;
            }
            if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].val < (swapIndex === null ? node.val : this.heap[swapIndex].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 minNode = minHeap.pop();
        current.next = minNode;
        current = current.next;
        if (minNode.next) {
            minHeap.push(minNode.next);
        }
    }
    
    return dummy.next;
}

总结

• 分治法：适合链表数量较少的情况，代码实现相对简单，时间复杂度为 O(N log K)。
• 优先队列（最小堆）：适合链表数量较多的情况，时间复杂度同样为 O(N log K)，但空间复杂度较高。

根据实际场景选择合适的算法，可以有效提升性能。