[leetCode]Merge k Sorted Lists

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

外部排序的基础

 1 #include <iostream>
 2 #include<vector>
 3 using namespace std;
 4 
 5 struct ListNode {
 6     int val;
 7     ListNode *next;
 8     ListNode(int x) : val(x), next(NULL) {}
 9 };
10 class Solution {
11 public:
12     static const int MAX = 9999;
13     ListNode *mergeKLists(vector<ListNode *> &lists) {
14         int listnum = checkListNum(lists);
15         ListNode *head,*tail;
16         head = tail = NULL;
17         while(listnum){
18             int index,min;
19             min = MAX;
20             index = 0;
21             for(int i = 0; i < lists.size();i++){
22                 if(lists[i] != NULL){
23                     if(lists[i]->val < min){
24                         min = lists[i]->val;
25                         index = i;
26                     }
27                 }
28             }
29             if(head == NULL){
30                 head = lists[index];
31                 tail = head;
32             }else{
33                 tail->next = lists[index];
34                 tail = tail->next;
35             }
36             lists[index] = lists[index]->next;
37             tail->next = NULL;
38             listnum = checkListNum(lists);
39         }
40         return head;
41     }
42     int checkListNum(vector<ListNode *> &lists){
43         int num = 0;
44         for(int i = 0; i < lists.size();i++){
45             if(lists[i] != NULL) num++;
46         }
47         return num;
48     }
49 };

艰难的成长