[leetcode题解]23.Merge K Sorted Lists(多链表合并)

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

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]23.Merge K Sorted Lists(多链表合并)

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/106.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注