Merge K Sorted Lists

题目：

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

Analyze and describe its complexity.

分析：

题目本身有两个逻辑上的事情需要注意：

1. 如果K个list里面有NULL，则不需要加入heap
2. 取出ListNode* temp = heap.top()之后，只有在temp->next != NULL的情况下才push回去

这题目的另一个重点是重载运算符，重载运算符这件事情还没有用明白！！！

此外，用divide and conquer的方法做一遍这道题目！！！

解法：

class Compare {
public:    
    bool operator() (ListNode* lhs, ListNode* rhs) {
        return (lhs->val > rhs->val);
    }
}; 

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
        if (lists.size() == 0) {
            return NULL;
        }

        if (lists.size() == 1) {
            return lists[0];
        }

        priority_queue<ListNode*, vector<ListNode*>, Compare > pQ;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                pQ.push(lists[i]);
            }
        }

        ListNode dummy(-1);
        ListNode* curr = &dummy;
        while (!pQ.empty() ) {
            ListNode* temp = pQ.top();
            pQ.pop();

            curr->next = temp;
            curr = temp;

            if (temp->next != NULL) {
                pQ.push(temp->next);
            }

        }
        return dummy.next;
    }
};