题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题解

递归 + MergeTwo

时间复杂度是 O(log(k) k n)，k 是 lists 中的 ListNode 数，n 是所有 ListNode 的平均长度。

public ListNode MergeKLists(ListNode[] lists)
{
    if (lists == null || lists.Length == 0) return null;
    return PartionMerge(lists, 0, lists.Length - 1);
}
private ListNode PartionMerge(ListNode[] lists, int low, int high)
{
    if (low >= high) return lists[low];
    var mid = low + (high - low) / 2;
    var l1 = PartionMerge(lists, low, mid);
    var l2 = PartionMerge(lists, mid + 1, high);
    return MergeTwoLists(l1, l2);
}
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val)
    {
        l1.next = MergeTwoLists(l1.next, l2);
        return l1;
    }
    l2.next = MergeTwoLists(l1, l2.next);
    return l2;
}