Leetcode23合并k个排序链表

23合并K个排序链表

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

示例:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

使用优先队列合并(递归版)
执行用时：580 ms
内存消耗：7.9 MB
找lists的头节点中最小的一个的环节可以优化

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize)
{
    struct ListNode *node;
    int n = 0, i = 0;
    while (n < listsSize)
    {
        if (lists[n] != NULL)
            break;
        else
            n++;
    }
    if (n == listsSize)
        return NULL;
    for (i = 0; i < listsSize; i++)
    {
        if (lists[i] != NULL && lists[n]->val > lists[i]->val)
            n = i;
    }
    node = lists[n];
    lists[n] = lists[n]->next;
    node->next = mergeKLists(lists, listsSize);
    return node;
}

Solution 2

使用优先队列合并(非递归版)
执行用时：552 ms
内存消耗：7.9 MB
找lists的头节点中最小的一个的环节可以优化

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize)
{
    struct ListNode _head;
    struct ListNode *head = &_head;
    struct ListNode *node = head;
    int n = 0, i = 0;
    _head.next = NULL;
    while (1)
    {
        for (n = 0; n < listsSize; n++)
            if (lists[n] != NULL)
                break;
        if (n == listsSize)
            break;
        for (i = 0; i < listsSize; i++)
        {
            if (lists[i] != NULL && lists[n]->val > lists[i]->val)
                n = i;
        }
        node->next = lists[n];
        node = node->next;
        lists[n] = lists[n]->next;
    }
    return head->next;
}