今天看啥
热点:

leetcode,leetcodeoj


题目:

Merge k Sorted Lists


Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 


分析:

用multiset作为小根堆,multiset的begin是value最小的结点。

注意:

1、由于我人为规定了multiset的排序方式(即用节点的value进行排序),使得两个不同的节点指针,若它们的value相等,则会被判断成“同一个节点”。而set是不允许重复值的,故以下代码不能使用set,而用multiset!

2、代码中我是用了multiset,实际上应该用小根堆的,只不过c++中没有现成的小根堆可用,便偷懒了。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
 struct mysort
 {
   bool operator()(const ListNode*const &a,const ListNode*const &b) const
   {
        return a->val<b->val;
   }
 };
 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int size=lists.size();
        multiset<ListNode*,mysort> table;
        for(int i=0;i<size;++i)
        {
            if(lists[i]!=nullptr)
                table.emplace(lists[i]);
        }
            
        ListNode helper(0),*cur=&helper;
        while(!table.empty())
        {
             ListNode* tmp=*table.begin();
            int smallest=tmp->val;
          
            cur->next=new ListNode(smallest);
            cur=cur->next;
          
           if(tmp->next==nullptr)
           {
               table.erase(table.begin());
           }
           else
            {
                 table.erase(table.begin());
                 table.emplace(tmp->next);
            }
        }       
        return helper.next;
    }
};


www.bkjia.comtruehttp://www.bkjia.com/ASPjc/1019937.htmlTechArticleleetcode,leetcodeoj 题目: Merge k Sorted Lists Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 分析: 用multiset作为小...

相关文章

相关搜索: c++ 程序员 面试 链表

帮客评论

视觉看点