leetcode,23题,Merge K Sorted Lists,多排序链表合并为一个有序链表问题。可以直接使用priority_queue或者heap。
多个链表以vector形式组织,vector中可能含有空链表,所以建堆或者初始化优先队列之前先对vector进行过滤,将空链表过滤掉。
注意优先队列的写法,类型,底层容器,以及要用到的比较器,比较器是一个重载了括号操作符的普通类。
c++题解:
class cmp { public: bool operator()(ListNode *pa, ListNode *pb) { return pa->val > pb->val; } }; class Solution { //author:凌风技术站-iaccepted public: ListNode* mergeKLists(vector<ListNode*>& lists) { //去除空链表 for (auto ite = lists.begin(); ite != lists.end();) { if (*ite == NULL)ite = lists.erase(ite); else ++ite; } priority_queue<ListNode *, vector<ListNode *>, \ cmp> pq(lists.begin(), lists.end()); ListNode *pre = new ListNode(-1); ListNode *tail = pre; //合并为一个链表 while(!pq.empty()) { ListNode *top = pq.top(); pq.pop(); tail->next = top; tail = tail->next; if (top->next != NULL) { pq.push(top->next); } } tail->next = NULL; return pre->next; } };
python题解:
from Queue import PriorityQueue class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode :author: 凌风技术站-iaccepted """ pq = PriorityQueue() for item in lists: if item is not None: pq.put((item.val, item)) pre = ListNode(-1) tail = pre while not pq.empty(): top = pq.get() tail.next = top[1] tail = tail.next l = top[1].next if l is not None: pq.put((l.val, l)) tail.next = None return pre.next
本文标题:[leetcode题解]23.Merge K Sorted Lists(多链表合并)
本文链接地址:https://www.iaccepted.net/algorithm/leetcode/106.html