[LeetCode]23.Merge k Sorted Lists

【题目】

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

【分析】

无

【代码】

/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：Time Limit Exceeded
*   来源：LeetCode
*   博客：
**********************************/
#include 
  
   
#include 
   
     using namespace std; struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; class Solution { public: ListNode *mergeKLists(vector
    
      &lists) { ListNode *head = NULL; if(lists.size() == 0){ return head; }//if for(int i = 0;i < lists.size();i++){ head = mergeTwoLists(head,lists[i]); }//for return head; } private: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } } }; // 创建链表 ListNode* CreateList(int A[],int n){ ListNode *head = NULL; if(n <= 0){ return head; }//if head = new ListNode(A[0]); ListNode *p1 = head; for(int i = 1;i < n;i++){ ListNode *node = new ListNode(A[i]); p1->next = node; p1 = node; }//for return head; } int main() { Solution solution; vector
     
       vecs; int A[] = {1,2,4,7,9}; int B[] = {3,5,8,10,11,12}; int C[] = {6,10,13}; int D[] = {15,16,17,23}; ListNode* head1 = CreateList(A,5); ListNode* head2 = CreateList(B,6); ListNode* head3 = CreateList(C,3); ListNode* head4 = CreateList(D,4); vecs.push_back(head1); vecs.push_back(head2); vecs.push_back(head3); vecs.push_back(head4); ListNode *head = solution.mergeKLists(vecs); // 输出 ListNode *p = head; while(p){ cout<
      
       val<<" "; p = p->next; }//while cout<
       
        
 这种方法超时。。。。。。。 
        
 
        
【分析二】
 
        
采用最小优先级队列。
 
        
第一步：把非空的链表装进最小优先级队列中。





 
        
第二步：遍历最小优先级队列，直到最小优先级队列空为止。每次遍历，都能从最小优先级队列中取出具有当前最小的元素的链表。
 
        
如果除最小元素之外，链表不空，重新装进最小优先级队列中。
 
        
【代码二】
 
        

        
/*********************************
*   日期：2015-01-06
*   作者：SJF0115
*   题目: 23.Merge k Sorted Lists
*   来源：https://oj.leetcode.com/problems/merge-k-sorted-lists/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include 
         
          
#include 
          
            using namespace std; struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; class Solution { public: ListNode *mergeKLists(vector
           
             &lists) { ListNode *head = new ListNode(-1); ListNode *p = head; // 最小优先级队列 priority_queue
            
             ,cmp> Heap; // 链表加入优先级队列 for(int i = 0;i < lists.size();i++){ if(lists[i] != NULL){ Heap.push(lists[i]); }//if }//for // merge while(!Heap.empty()){ // 最小的 ListNode *list = Heap.top(); Heap.pop(); p->next = list; p = list; if(list->next != NULL){ Heap.push(list->next); }//if }//while return head->next; } private: // 用于最小优先级队列 struct cmp { bool operator()(ListNode* node1, ListNode* node2) { return node1->val > node2->val; }//bool }; }; // 创建链表 ListNode* CreateList(int A[],int n){ ListNode *head = NULL; if(n <= 0){ return head; }//if head = new ListNode(A[0]); ListNode *p1 = head; for(int i = 1;i < n;i++){ ListNode *node = new ListNode(A[i]); p1->next = node; p1 = node; }//for return head; } int main() { Solution solution; vector
             
               vecs; int A[] = {1,2,4,7,9}; int B[] = {3,5,8,10,11,12}; int C[] = {6,10,13}; int D[] = {15,16,17,23}; ListNode* head1 = CreateList(A,5); ListNode* head2 = CreateList(B,6); ListNode* head3 = CreateList(C,3); ListNode* head4 = CreateList(D,4); vecs.push_back(head1); vecs.push_back(head2); vecs.push_back(head3); vecs.push_back(head4); ListNode *head = solution.mergeKLists(vecs); // 输出 ListNode *p = head; while(p){ cout<
              
               val<<" "; p = p->next; }//while cout<