当前位置: 面试刷题>> 合并 K 个升序链表(经典算法150题)


题目描述

合并 k 个升序链表,将 k 个升序链表合并为一个新的升序链表并返回。其中每个链表节点的定义如下(以 Python 为例,但其他语言类似):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

给定 k 个链表的头节点数组 heads,其中 heads[i] 是链表中第 i 个链表的头节点。

示例

输入

# 链表 1: 1->4->5
# 链表 2: 1->3->4
# 链表 3: 2->6
heads = [ListNode(1, ListNode(4, ListNode(5))), ListNode(1, ListNode(3, ListNode(4))), ListNode(2, ListNode(6))]

输出

合并后的链表为:1->1->2->3->4->4->5->6

解题思路

有多种方法可以解决这个问题,包括使用优先队列(最小堆)来持续追踪所有链表当前的最小节点,或者使用分治法(将链表两两合并,直到合并为一个链表)。这里我们使用优先队列(最小堆)的方法,因为它在处理这类问题时通常更加高效。

PHP 示例代码

PHP 不直接支持优先队列,但我们可以使用 SplPriorityQueue 来模拟。

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function mergeKLists($heads) {
    $pq = new SplPriorityQueue();
    $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

    // 初始化优先队列
    foreach ($heads as $head) {
        if ($head !== null) {
            $pq->insert([$head->val, $head], $head->val);
        }
    }

    $dummy = new ListNode(0);
    $current = $dummy;

    while (!$pq->isEmpty()) {
        list($val, $node) = $pq->extract();
        $current->next = $node;
        $current = $current->next;

        if ($node->next !== null) {
            $pq->insert([$node->next->val, $node->next], $node->next->val);
        }
    }

    return $dummy->next;
}

Python 示例代码

Python 使用 heapq 模块来实现优先队列。

import heapq

def mergeKLists(heads):
    dummy = ListNode(0)
    current = dummy
    heap = []

    # 初始化堆
    for head in heads:
        if head:
            heapq.heappush(heap, (head.val, head))

    while heap:
        val, node = heapq.heappop(heap)
        current.next = node
        current = current.next

        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))

    return dummy.next

JavaScript 示例代码

JavaScript 可以通过数组模拟优先队列,并使用 Array.prototype.sort() 来维护堆的性质。

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function mergeKLists(heads) {
    let dummy = new ListNode(0);
    let current = dummy;
    let heap = [];

    // 初始化堆
    for (let head of heads) {
        if (head) {
            heap.push({ val: head.val, node: head });
        }
    }

    heap.sort((a, b) => a.val - b.val); // 初始排序

    while (heap.length > 0) {
        let { val, node } = heap.shift();
        current.next = node;
        current = current.next;

        if (node.next) {
            heap.push({ val: node.next.val, node: node.next });
            heap.sort((a, b) => a.val - b.val); // 每次插入后重新排序
        }
    }

    return dummy.next;
}

注意:JavaScript 示例中的堆实现不是最高效的,因为它在每次插入后都进行了全排序。在实际应用中,你可能需要使用更高效的堆实现,如二叉堆。不过,为了简化示例,这里使用了简单的数组和排序函数。

推荐面试题