Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

http://www.lintcode.com/en/problem/merge-k-sorted-lists/

Discussion

这个题有多重解法。至少要会暴力法。还有堆排序，和分治法。

Solution 1

Brute force。每次合并两个链表，合并k-1次。每次合并两个长度为n最多需要比较2n次，假设每个链表长度为n，那么总共比较次数就是$$2n+3n+...+kn = O(nk^2)$$. O(1) space.

class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        int n = lists.size();
        //if (n==0) return NULL;
        ListNode *result = NULL;
        for(int i=0; i<n; i++) {
            result = mergeTwoLists(result, lists[i]);
        }
        return result;
    }
private:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy  = ListNode(0);
        ListNode *curr = &dummy;
        while (l1 && l2) {
            if(l1->val < l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        curr->next = l1? l1:l2;
        return dummy.next;
    }
};

Solution 2

Heap. The standard container adaptor priority_queue calls make_heap, push_heap and pop_heap automatically to maintain heap properties for a container.

要会用priority_queue. 看这篇文章。默认的priority_queue是大的数on top, 需要自定义comparison object.

维护一个k个大小的最小堆，初始化堆中元素为每个链表的头结点，每次从堆中选择最小的元素加入到结果链表，再选择该最小元素所在链表的下一个节点加入到堆中。这样当堆为空时，所有链表的节点都已经加入了结果链表。每次加入一个新元素，pop出一个元素，复杂度为O（logk），总共有kn个元素加入堆中，因此，复杂度是O（nklogk）。

堆：找最大最小方便，O(1)插入, O(logn)删除， O(n)建堆。。

class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        priority_queue<ListNode*, vector<ListNode*>, mycom> myque;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
        for(int i=0; i<lists.size(); i++) {
            if(lists[i])
                myque.push(lists[i]);
        }
        while(!myque.empty()) {
            ListNode *p = myque.top();
            cur->next = p;
            myque.pop();
            cur = cur->next;
            if(p->next) {//加入该节点的下一个节点
                myque.push(p->next);
            }
        }
        return dummy.next;
    }
private:
    struct mycom{//self defined comparison object
        bool operator() (ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };
};