Merge K Sorted List

LeetCode #23

Description:

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

Example:

Note

Idea:

1. 典型的merge sort思想。

Time: O(nklogk)

1. 也可以用min heap来搞，创建一个heap，k size，每个list push进第一元素，然后heap pop，对应的list再进一个（如果not empty），指导heap为空。

Time: O(nklogk)

Code:

Divide and Conquer

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;

        int n=lists.size();
        mergeDivide(lists, 0, n-1);

        return lists[0];
    }

    // 就是merge sort
    void mergeDivide(vector<ListNode*>& lists, int left, int right){
        if(left < right){
            int mid=left+(right-left)/2;
            mergeDivide(lists, left, mid);
            mergeDivide(lists, mid+1, right);
            lists[left]=mergeTwoLists(lists[left], lists[mid+1]);
        }
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL || l2==NULL) return l1==NULL? l2 : l1;
        ListNode dummy(-1);

        ListNode * curr = &dummy;
        while(l1!=NULL && l2!=NULL){
            if(l1->val<=l2->val){
                curr->next=l1;
                l1=l1->next;
            }
            else{
                curr->next=l2;
                l2=l2->next;
            }
            curr=curr->next;
        }

        curr->next = l1==NULL? l2: l1;

        return dummy.next;
    }
};