首页 > 代码库 > [leetcode]Merge k Sorted Lists

[leetcode]Merge k Sorted Lists

use smaller heap

 

/** * 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) {        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)> >             que([&](ListNode* a, ListNode* b) {return a->val > b->val;});        for (int i = 0; i < lists.size(); i++) {            if (lists[i]) que.push(lists[i]);        }        ListNode* dummy = new ListNode(-1);        ListNode* curr = dummy;        while(!que.empty()) {            curr->next = que.top();            curr = curr->next;            que.pop();            if (curr->next) {                que.push(curr->next);            }            curr->next = nullptr;        }        return dummy->next;    }};

 

[leetcode]Merge k Sorted Lists