23. 合并 K 个升序链表

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/

代码

/**
 * Definition for singly-linked list.
 * 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)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    let res = null;
    for(let i = 0; i < lists.length; i++){
        res = merge2Lists(res, lists[i]);
    }
    return res;
};

function merge2Lists(list1: ListNode | null, list2: ListNode | null){
    let dummy = new ListNode();
    let head = dummy, head1 = list1, head2 = list2;
    while(head1 && head2){
        if(head1.val < head2.val){
            head.next = head1;
            head1 = head1.next;
        }
        else{
            head.next = head2;
            head2 = head2.next;
        }
        head = head.next;
    }
    head.next = head1 ? head1: head2;
    return dummy.next;
}

思路

使用顺序合并的方法，逐个合并链表：

主要步骤

1. 初始化结果链表 res = null
2. 遍历 lists 数组，依次将每个链表与结果链表合并
3. 使用辅助函数 merge2Lists 合并两个有序链表

辅助函数 merge2Lists

合并两个有序链表的经典方法：

1. 创建哑节点 dummy 作为结果链表的起始点
2. 使用指针 head 指向当前构建位置
3. 比较两个链表的当前节点，选择较小的连接到结果链表
4. 当其中一个链表遍历完后，直接连接另一个链表的剩余部分
5. 返回 dummy.next

复杂度分析

假设有 $k$ 个链表，每个链表平均长度为 $n$：

• 第一次合并：$O(n)$

• 第二次合并：$O(2n)$

• 第 $k$ 次合并：$O(kn)$

• 总时间复杂度：$O(k^{2}n)$

• 时间复杂度 $O(k^{2}n)$，其中 $k$ 是链表数量，$n$ 是平均链表长度

• 空间复杂度 $O(1)$