[LeetCode] Merge k Sorted Lists - c++编程基础

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

问题描述：给定k个已经排序的链表，将它们合并成一个排序的链表。

这道题暂时没有想出其它优化的办法，就用比较笨的办法先做。

遍历k个链表，取最小值，然后将这个最小值的节点取出来，放到结果链表中。时间复杂度为O(k*n)。

注意要考虑链表为空的情况。

class Solution {  
public:  
    ListNode *mergeKLists(vector &lists) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(lists.size() == 0)  
            return NULL;  
          
        int min_ele = INT_MAX;  
        ListNode *head = NULL, *p = NULL, *q = NULL;  
        vector::iterator liter;  
        while(lists.size()) {  
            for(vector::iterator iter = lists.begin();  
                                             iter != lists.end(); ++iter) {  
                if(*iter == NULL) {  
                    iter = lists.erase(iter);  
                    --iter;  
                }                                       
            }  
              
            vector




::iterator iter;  
            min_ele = INT_MAX;  
            for(iter= lists.begin();  
                iter != lists.end(); ++iter) {  
                if((*iter) != NULL && ((*iter)->val) < min_ele) {  
                    liter = iter;  
                    min_ele = ((*iter)->val);  
                }                                       
            }  
            if(min_ele != INT_MAX) {  
                p = *liter;  
                *liter = p->next;  
                p->next = NULL;  
                if(head == NULL) {  
                    head = p;  
                    q = head;  
                }  
                else {  
                    q->next = p;  
                    q = q->next;  
                }  
            }  
        }  
          
        return head;  
    }  
};