本文共 2460 字，大约阅读时间需要 8 分钟。

struct ListNode {	int val;	ListNode *next;	ListNode(int x) : val(x), next(NULL) {}};class Solution {//O(nlogk)//using priority_queue to choose current minimum node//node: keep priority_queue free of NULL pointerpublic:	struct PQNode	{		int index;		ListNode* ptr;		PQNode(int _index = 0, ListNode* _ptr = NULL):index(_index),ptr(_ptr){}	};	struct Comp	{		bool operator()(const PQNode& lhs, const PQNode& rhs) const		{			return lhs.ptr->val > rhs.ptr->val;		}	};	ListNode *mergeKLists(vector
   
     &lists) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		priority_queue
    
     , Comp> pq;		ListNode* head = NULL;		ListNode* cur = NULL;		do		{			for(int i = 0; i < lists.size(); ++i)			{				if(lists[i] != NULL)				{					pq.push(PQNode(i, lists[i]));					lists[i] = lists[i]->next;				}			}			if(pq.empty()) break;			if(head == NULL)				head = pq.top().ptr;			else 				cur->next = pq.top().ptr;			cur = pq.top().ptr;			int curIdx = pq.top().index;			pq.pop();			if(lists[curIdx] != NULL)			{				pq.push(PQNode(curIdx, lists[curIdx]));				lists[curIdx] = lists[curIdx]->next;			}		}while(true);		if(cur != NULL) cur->next = NULL;		return head;	}};
    
   

second time

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    struct Node    {        ListNode* pNode;        int listIdx;        Node(ListNode* _pNode = NULL, int _listIdx = 0):pNode(_pNode), listIdx(_listIdx){};        bool operator < (const Node& orh) const {return pNode->val > orh.pNode->val;};    };    ListNode *mergeKLists(vector
   
     &lists) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        priority_queue
    
      pq;        ListNode dummy(-1);        ListNode* prev = &dummy;        for(int i = 0; i < lists.size(); ++i)            if(lists[i] != NULL) pq.push(Node(lists[i], i)), lists[i] = lists[i]->next;                    while(!pq.empty())        {            prev->next = pq.top().pNode;//top() return the first element in pq            prev = prev->next;            int listIdx = pq.top().listIdx;            pq.pop();            if(lists[listIdx] != NULL)             {                pq.push(Node(lists[listIdx], listIdx));                lists[listIdx] = lists[listIdx]->next;            }        }                prev->next = NULL;        return dummy.next;    }};
    
   

转载地址：http://qlxti.baihongyu.com/