023 - Merge k Sorted Lists

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Hide Tags
Divide and Conquer Linked List Heap
Hide Similar Problems
(E) Merge Two Sorted Lists
 
开始想用堆，但对于从k个链表怎么选下一个值加入堆没想清楚，所以用分治做了，类似merge sort，没啥好说的。

/**
* 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) {
        int sz = lists.size();
        return (sz>1) ? dvd(lists, 0, sz-1) : (sz ? lists[0] : NULL);
    }
   
    ListNode* dvd(vector<ListNode*>& lists, int start, int end)
    {
        if(start==end)
            return lists[start];
        if(start==end-1)
            return mergee(lists[start], lists[end]);
       
        int mid=(start+end)>>1;
        return mergee(dvd(lists, start, mid), dvd(lists, mid+1, end));
    }
   
    ListNode* mergee(ListNode* a, ListNode* b)
    {
        ListNode dummy(0);
        ListNode* p = &dummy;
        while(a && b)
        {
            if((a->val) > (b->val))
                p->next = b, b=b->next;
            else
                p->next = a, a=a->next;
            p = p->next;
        }
        p->next = a ? a : b;
        return dummy.next;
    }
};
408 ms.

做完了跑去看了看讨论区，有人用堆，每pop一个堆顶的值，就push它的next，NND就这里脑塞，愚钝！！
附上用堆实现的过程，原帖在此。

struct Comp{ bool operator()(const ListNode * a, const ListNode * b){ return a->val > b->val; } }; class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.size() == 0) return NULL; std::priority_queue<ListNode *, vector<ListNode *>, Comp> minHeap; //push the first nodes of each list into the minHeap int numLists = lists.size(); for (int i = 0; i < numLists; i++) { ListNode *ln = lists[i]; if (ln != NULL) minHeap.push(ln); } //if the minHeap is still 0 then exit if (minHeap.size() == 0) return NULL; //set the head of the link list to the top of the minHeap ListNode *head = minHeap.top(); ListNode *node = head; //iterate while there's still something in the minHeap while (minHeap.size()) { //get the top node ListNode *currNode = minHeap.top(); minHeap.pop(); //if this node has a next node, then push that into the minHeap if (currNode->next != NULL) minHeap.push(currNode->next); //remove the node from the link list that it's a part of node->next = currNode; node = node->next; node->next = NULL; } return head; } };
420 ms.