cztchoice
1/21/2014 - 2:54 PM

Merge k Sorted Lists This Solution is not time efficient, the best time complexity is o(n*logk), this one is o(n * k) http://oj.leetcode.c

Merge k Sorted Lists This Solution is not time efficient, the best time complexity is o(n*logk), this one is o(n * k) http://oj.leetcode.com/problems/merge-k-sorted-lists/

merge-k-sorted-lists.cpp
content_copyfile_download
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isEmpty(const vector<ListNode *> &lists){
        for(int i = 0; i < lists.size(); i++){
            if(lists[i]){
                return false;
            }
        }
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size() == 0){
            return NULL;
        }
        ListNode *head = NULL;
        bool set_head = false;
        
        ListNode *it;
        int min_i = 0;
        int min_val = 0;
        int i = 0;
        while(true){
            bool set_min = false;
            for(int i = 0; i < lists.size(); i++){
                if(lists[i]){
                    if(!set_min){
                        min_i = i;
                        min_val = lists[i]->val;
                        set_min = true;
                    }
                    else{
                        if(lists[i]->val < min_val){
                            min_i = i;
                            min_val = lists[i]->val;
                        }
                    }
                }
            }
            if(!set_min){
                break;
            }
            ListNode *temp = lists[min_i];
            lists[min_i] = lists[min_i]->next;
            if(!set_head){
                head = temp;
                set_head = true;
                it = head;
            }
            else{
                it->next = temp;
                it = it->next;
                it->next = NULL;
            }
        }
        return head;
    }
};