题解 | #合并k个已排序的链表#

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    class min{
        public:
        min(int v,int l1){
            value=v;
            location1=l1;
        }
        public:
        int value;
        int location1;
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        vector<int> location;
        int length=lists.size();
//         cout<<length;
//         cout<<lists[1]->val;
        for(int i=0;i<length;i++){
            location.push_back(0);
        }
        int count=length;
        min* min1=new min(1001,0);
        min* min2=new min(1001,0);
        ListNode* merge=new ListNode(0);
        ListNode*p=merge;
        while(count>=0){
            for(int i=0;i<length;i++){
                if(lists[i]!=NULL){
                     if(lists[i]->val<min2->value){
                         if(lists[i]->val<min1->value){
                             min2->value=min1->value;
                             min2->location1=min1->location1;
                             min1->value=lists[i]->val;
                             min1->location1=i;
//                              cout<<"存1";
                         }
                         else{
                             min2->value=lists[i]->val;
                             min2->location1=i;
//                              cout<<"存2";
                         }
                     }
                }
            }
            if(min1->value==1001) break;
            if(lists[min1->location1]->next!=NULL){
               if(lists[min1->location1]->next->val<min2->value){
                   min2->value=lists[min1->location1]->next->val;
                   min2->location1=min1->location1;
               }
            }
            if(min1->value!=1001){
                ListNode* p1=new ListNode(min1->value);
                lists[min1->location1]=lists[min1->location1]->next;
                p->next=p1;
                p=p->next;
                min1->value=1001;
                if(lists[min1->location1]==NULL) count-=1;
            }
            if(min2->value!=1001){
                ListNode* p2=new ListNode(min2->value);
                lists[min2->location1]=lists[min2->location1]->next;
                p->next=p2;
                p=p->next;
                min2->value=1001;
                if(lists[min2->location1]==NULL) count-=1;
            }
            p->next=NULL;
        }
        return merge->next;
    }
};

以上为c++代码，时间复杂度和空间复杂度都较低，因为采用一次记入两个最小值量，遍历lists表读取，读取出数后将lists表对应的链表后移，同时存入1001覆盖最小值（因为val取值低于1001） 可以看出结果是不错的