23. 合并K个排序链表

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

Solution1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool cmp(const ListNode* a,const ListNode *b){
    return a->val < b->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        std::vector<ListNode*> node_vec;
        //将每个结点push到vec中。
        for(int i = 0; i < lists.size(); i++){
            ListNode* head = lists[i];
            while(head){
                node_vec.push_back(head);
                head = head->next;
            }
        }
        if(node_vec.size() == 0){
            return NULL;
        }
        //将vec中的元素按val域排序。
        std::sort(node_vec.begin(),node_vec.end(),cmp);
        //链接各个结点。
        for(int i = 1;i < node_vec.size();i++){
            node_vec[i-1]->next = node_vec[i];
        }
        //最后一个结点指向NULL
        node_vec[node_vec.size()-1]->next = NULL;
        return node_vec[0];
    }
};

该方法比较粗暴。将所有的结点存入一个vector中，按结点中的值排序，然后依次将每个结点链接，最后返回。

Solution2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode p0 = ListNode(0);
        ListNode* p = &p0;
        ListNode* p1 = p;
        while(l1 && l2){
            if(l1->val < l2->val){
                p->next = new ListNode(l1->val);
                p = p->next;
                l1 = l1->next;
            }else{
                new ListNode(l2->val);
                p->next = new ListNode(l2->val);
                p = p->next;
                l2 = l2->next;
            }
        }
        p->next = (l1!=NULL) ? l1 :(l2!=NULL) ? l2 : NULL;
        return p1->next;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //两个终止条件。
        if(lists.size() == 0){
            return NULL;
        }
        if(lists.size() == 1){
            return lists[0];
        }
        
        //将lists拆分成两个子lists;
        int mid = lists.size()/2;
        std::vector<ListNode*> sub1_lists;
        std::vector<ListNode*> sub2_lists;
        for(int i = 0; i < mid; i++){
            sub1_lists.push_back(lists[i]);
        }
        for(int i = mid; i < lists.size(); i++){
            sub2_lists.push_back(lists[i]);
        }
        //递归调用
        ListNode *l1 = mergeKLists(sub1_lists);
        ListNode *l2 = mergeKLists(sub2_lists);
        //返回两个链表合并的结果。
        return mergeTwoLists(l1,l2);
    }
};
思路:

（归并思想）递归算法。
将k个链表分割为独立的链表，再向上两两合并。

合并两个有序链表的子问题参照：
21. 合并两个排序链表