地址

https://leetcode.com/problems/merge-k-sorted-lists/description/

题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路

1.分治：很容易想到分治，就像一个二叉树从下往上跑
2.平衡树：既然想到了二叉树，那么用平衡树自然也可以。把所有的序列的值都插入到树上，然后一次性加到链表中。c++中用multiset替代。
3.优先队列/堆：这也是一个很基础的想法，每次从k个链表中取出一个最小值即可。这个方法的关键是如何在短时间内从k个链表中找出最小的那个，显然可以用优先队列or堆。

代码

/**
 * 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) {
        multiset<int>st;
        for(auto vc:lists)
        for(ListNode* it=vc;it!=NULL;it=it->next)
            st.insert(it->val);
        ListNode *ret = new ListNode(0),*p = ret;
        for(auto it=st.begin();it!=st.end();it++)
        {
            p->next = new ListNode(*it);
            p=p->next;
        }
        return ret->next;
    }
};