把k个已经sort了的linked list合并成一个linked list. key words: priority_queue

23. Merge k Sorted Lists.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    class CompareListNode{
    public:
        bool operator()(ListNode* a ,ListNode* b){
            if (a->val > b->val) return true;
            else return false;
        }
    };

    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> index(lists.size());
        ListNode* res = new ListNode(0);
        ListNode* current = res;
        priority_queue<ListNode*,vector<ListNode*>,CompareListNode> pq;
        
    
        for (ListNode* list: lists){
            if (list) pq.push(list);
        }
    

        while (!pq.empty()){
            ListNode* newNode = pq.top();
            current->next = newNode;
            current = newNode;
            pq.pop();
            if (newNode->next) pq.push(newNode->next);
        }
        return res->next;
    }
    

};

Priortity_Queue.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    class CompareListNode{
    public:
        bool operator()(ListNode* a ,ListNode* b){
            return a->val > b->val;//一行代码直接return boolean value.
        }
    };

    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> index(lists.size());
  
        priority_queue<ListNode*,vector<ListNode*>,CompareListNode> pq;
        
        for (ListNode* list: lists){
            if (list) pq.push(list);
        }
        
        if (pq.empty()) return NULL;
        
        ListNode* res = pq.top();
        pq.pop();
        ListNode* current = res;
        if (res->next) pq.push(res->next);
    
        while (!pq.empty()){ //这里和我的code相比就有简化，不需要新搞一个ListNode*
            current->next = pq.top();
            current = current->next;
            pq.pop();
            if (current->next) pq.push(current->next);
        }
        return res;
    }
    

};

一些编程里的小tips:
_直接用 return l->val > r->val来省去if的麻烦。
*result可以直接从pq.top()开始,而不需要先创建一个new ListNode_然后return它的next.(但是这样也会在开始的时候先压入一个pq的top())