LeetCode题目之腾讯精选练习（50题）：合并K个排序链表

题目

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

示例:

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

实现代码

public ListNode MergeKLists(ListNode[] lists)
{
    var listHead = new ListNode(0);
    ListNode curr = listHead;
    int min, temp, minList = 0;
    while (lists.Any(i => i != null))
    {
        min = int.MaxValue;
        for (int i = 0; i < lists.Length; i++)
        {
            if (lists[i] == null)
                continue;
            temp = lists[i].val;
            if (temp < min)
            {
                min = temp;
                minList = i;
            }
        }
        curr.next = new ListNode(min);
        lists[minList] = lists[minList].next;
        curr = curr.next;
    }
    return listHead.next;
}
           

执行结果

执行结果：通过

执行用时 : 796 ms, 在所有 C# 提交中击败了17.14%的用户

内存消耗 : 27.6 MB, 在所有 C# 提交中击败了8.51%的用户

小的总结

开始对合并两个有序链表进行了改进，变成了合并k个有序链表，结果虽然通过，但是效率不是很高。之后看解答了解到了分治法，直接对之前的函数调用，进行两两合并，效率更加高。

改进的方法

分治法：

public ListNode MergeKLists(ListNode[] lists)
{
    int len = lists.Length;
    int interval = 1;
    while (interval < len)
    {
        for (int i = 0; i < len - interval; i += interval * 2)
        {
            lists[i] = MergeTwoLists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }
    if (len > 0)
        return lists[0];
    else
        return null;
}
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    var listHead = new ListNode(0);
    ListNode curr = listHead;
    int x, y;
    while (l1 != null || l2 != null)
    {
        x = (l1 != null) ? l1.val : int.MaxValue;
        y = (l2 != null) ? l2.val : int.MaxValue;
        if (x < y)
        {
            curr.next = new ListNode(x);
            if (l1 != null) l1 = l1.next;
        }
        else
        {
            curr.next = new ListNode(y);
            if (l2 != null) l2 = l2.next;
        }
        curr = curr.next;
    }
    return listHead.next;
}
           

执行结果