题目

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

示例:

输入:

[1->4->5, 1->3->4, 2->6]

输出: 1->1->2->3->4->4->5->6

来源：力扣（LeetCode）

题解

这道题一共有5种官方解法，每种解法都对应不同的水平。
分别是：

1. 暴力遍历法
2. 逐一比较法
3. 优先队列法
4. 逐一合并法 & 分治+合并法

暴力遍历法

暴力遍历法思想很简单，即为多个链表转化为一个数组，对数组进行排序后再将数组转化为链表。因为链表转化为数组是O(N)，而数组转化为链表也是O(N)，所以我觉得这里头影响最大的就是排序算法。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> arr;
        int k = lists.size();
        for (int i = 0; i < k; i++) {
            ListNode *p = lists[i];
            while (p != nullptr) {
                arr.push_back(p->val);
                p = p->next;
            }
        }

        sort(arr.begin(), arr.end());

        ListNode head(-1), *p;
        p = &head;
        for (int i = 0; i < arr.size(); i++) {
            p->next = new ListNode(arr[i]);
            p = p->next;
        }
        return head.next;
    }
};

执行用时 : 32 ms, 在所有 C++ 提交中击败了97.09%的用户
内存消耗 :11.6 MB, 在所有 C++ 提交中击败了67.33%的用户

逐一合并法 & 分治+合并法

逐一合并法，即按照顺序将第1个链表与之后的每个链表合并。需要用到之前写过的合并两个有序链表的方法作为核心合并算法，并且合并算法的快慢差距在这题里面更加的放大了。由于逐一合并法和分治合并法对链表的合并次数都相同，而逐一合并法的算法分析结果是O(kN)（N为总节点数），而分治法的算法分析结果是O(NlogN)。所以选取分治合并法。

其中k和logN的差距点在于，逐一合并法里面，对于已经合并排序过的节点在之后的合并排序中都会排序一次，而分治合并则在前面第一趟分治中有没重复运算的节点，所以就更加的节约了时间。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge2Lists(ListNode *l1, ListNode *l2) {
        ListNode head(0);
        register ListNode *o = &head;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                o->next = l1;
                l1 = l1->next;
            } else {
                o->next = l2;
                l2 = l2->next;
            }
            o = o->next;
        }
        if (l1) {
            o->next = l1;
        } else if (l2) {
            o->next = l2;
        }
        return head.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        register int step = 1, k = lists.size();

        if (k == 0) {
            return NULL;
        } else if (k == 1) {
            return lists[0];
        } else if (k == 2) {
            return merge2Lists(lists[0], lists[1]);
        }

        while (step < k) {
            for (int i = 0; i < k-step; i+=step*2) {
                lists[i] = merge2Lists(lists[i], lists[i+step]);
            }
            step *= 2;
        }
        return lists[0];
    }
};

执行用时 :32 ms, 在所有 C++ 提交中击败了97.12%的用户
内存消耗 : 10.7 MB, 在所有 C++ 提交中击败了98.35%的用户