Merge k Sorted Lists

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

Tag: divide and conquer, linked list, heap

update 9/22/2015

Merge sort the k lists. O(knlogk) in time, O(1)

//merge these 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL;
        return _mergeKLists(lists, 0, lists.size());
    }
    
    //not include end, include start
    ListNode * _mergeKLists(vector<ListNode*>& lists, int start, int end){
        //base case
        if(end - start == 1){
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode * l1 = _mergeKLists(lists, start, mid);
        ListNode * l2 = _mergeKLists(lists, mid, end);
        
        ListNode dummyNode = ListNode(0);
        ListNode *tail = &dummyNode;
        while(l1 != NULL && l2 != NULL){
            ListNode*& p = l1->val < l2->val ? l1: l2;
            tail->next = p;
            tail = tail->next;
            p = p->next;
        }
        tail->next = l1 == NULL? l2: l1;
        return dummyNode.next;
    }
};

遇到的第一个hard题，果然够味道。

版本一，用暴力搜，每次从k个lists中找到最小值，链到result里，再更新最小值所在的list。

空间复杂度O(1)，时间复杂度大约为O(k*k*n)。k为lists数，n为每个list里平均元素数。

解决了输入为空的问题，版本一遇到了超时。(Time Limit Exceeded)

挂在了k很大的一个测试上。

[{7},{49},{73},{58},{30},{72},{44},{78},{23},{9},{40},{65},{92},{42},{87},{3….大约有几千个。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode * head = NULL;
        ListNode * tail = NULL;
        ListNode * p = NULL;
        vector<ListNode *>::iterator it,idx;
        //lists is empty
        if (lists.empty()){
            return NULL;
        }
        
        //some listnode are empty
        if (lists.size() > 0){
            for(it = lists.begin(); it != lists.end(); it++){
                if (*it == NULL){
                    lists.erase(it);
                    it--; // this is important, since iterator should be decreased after erase operation
                }
            }
        }
        
        while(lists.size() > 0){
            int min = lists[0]->val;
            idx = lists.begin();
            for(it = lists.begin() + 1; it != lists.end(); it++){
                if ((*it)->val < min){
                    min = (*it)->val;
                    idx = it;
                }
            }
            
            if (head == NULL){
                head = tail = *idx;
            }
            else{
                tail->next = *idx;
                tail = *idx;
            }
            if ((*idx)->next == NULL){
                lists.erase(idx);
            }
            else{
                *idx = (*idx)->next;
            }
            
        }
        return head;
    }
};

1.20更新：

看了tag，发现要用堆来做。今天复习了分析算法时间复杂度和堆的知识，自己实现了一个堆算法。又学了stl中堆的用法（priority queue）。解决了这道题目。

其中要注意，利用priority_queue时，要查它的函数说明http://en.cppreference.com/w/cpp/container/priority_queue

自己写一个compare类，重载'()’操作符，完成自己的比较需求。

版本二：

利用堆排序，每次取出堆顶元素后，向后移动元素所在listnode的指针，如果为空的话则舍弃，如果不空的话重新插入堆中。不断维护该堆。

记n为每个list中的平均元素个数，k为list数

时间复杂度为O(k*n*logk)，空间复杂度为O(k)

C++代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class cmp
{
public:
    bool operator()(const ListNode * p1, const ListNode * p2) const{
        if (p1->val <= p2->val){
            return false;
        }
        
        else{
            return true;
        }
    }
};
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        vector<ListNode *>::iterator it;
        
        ListNode * head = NULL;
        ListNode * tail = NULL;
        ListNode * p = NULL;
        //lists is empty
        if (lists.empty()){
            return NULL;
        }
        
        //some elements in lists are empty
        for(it = lists.begin(); it != lists.end(); it++){
            if (*it == NULL){
                lists.erase(it);
                it--;
            }
        }
        
        if(lists.empty()){
            return NULL;
        }
        
        priority_queue<ListNode *, vector<ListNode *>, cmp>pq(cmp(), lists);
        
        //handle the first element
        p = pq.top();
        pq.pop();
        head = tail = p;
        p = p->next;
        if (p != NULL){
            pq.push(p);
        }
        
        //loop all the elements
        while(!pq.empty()){
            p = pq.top();
            pq.pop();
            
            tail->next = p;
            tail = tail->next;
            
            p = p->next;
            if(p != NULL){
                pq.push(p);
            }
        }
        
        tail->next = NULL;
        return head;
        
    }
        
};

程序运行效率

待完善：
用分治算法。