精华内容
下载资源
问答
  • 实现方法其实和普通的归并排序差不多,最大的区别是这里我们每一次合并只需要处理两个链表就行了。 class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()=...

    Leetcode第23题,一道hard题。
    leetcode 23

    1.分治法
    实现方法其实和普通的归并排序差不多,最大的区别是这里我们每一次合并只需要处理两个链表就行了。

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0)return 0;
            mergelist(lists,0,lists.size());  
            return lists[0];
        }
        
        void mergelist(vector<ListNode*>& lists,int l,int r)
        {
            if(r-l<2)return;
            auto mid=l+(r-l)/2;
            mergelist(lists,l,mid);
            mergelist(lists,mid,r);
            lists[l]=mergeTwoLists(lists[l],lists[mid]);
            
        }
        
       ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
         if(l1==0)return l2;
         if(l2==0)return l1;
         auto res=l1;
         ListNode* pre=0;
            while(l1&&l2)
            {
                if(l1->val>=l2->val)
                {
                    if(pre)
                    {  
                        auto temp=l2->next;
                        pre->next=l2;
                        l2->next=l1;
                        pre=l2;
                        l2=temp;
                    }
                    else 
                    {
                        auto temp=l2->next;
                        l2->next=l1;
                        pre=l2;
                        res=l2;
                        l2=temp;
                    }
                }
                else
                {
                     pre=l1;
                    l1=l1->next;   
                }
                
            }
          if(l2) pre->next=l2;
          return res;    
        }
        
    };
    

    2.优先级队列

    这里我们直接将每一个链表的首节点加入优先级队列中,因此需要定义一个比较函数对象cmp;
    然后进入循环每次取出堆顶元素(链表的某个节点),如果该节点存在下一个节点那么将其加入堆。

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0)return 0;
            auto cmp=[](ListNode*p1,ListNode*p2){return p1->val>p2->val;};
            priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)>heap(cmp);
             ListNode* head=0;
             auto pre=head;
            for(auto c:lists)
            {   
                if(c)
                heap.push(c);   
            }
            
            while(!heap.empty())
            {
                auto x=heap.top();
                heap.pop();
                if(head==0)
                {
                    head=x;
                    pre=x;
                }
                 else 
                 { 
                  pre->next=x;
                  pre=x;
                 }           
              if(x&&x->next) heap.push(x->next);  
            }
            return head;
        }
    };
    
    展开全文
  • //合并k个 ListNode* mergeKLists(vector*>& lists) { if(lists.size()==0) return NULL; if(lists.size()==1) return lists[0]; if(lists.size()==2) return mergeTwoLists(lists[0],lists[1]); int mid=...

    分治大法

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        //合并两个
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode temp_head(0);    //临时头结点
            ListNode *pre=&temp_head;
            while(l1&&l2){
                if(l1->val<l2->val){
                    pre->next=l1;
                    l1=l1->next;
                }else{
                    pre->next=l2;
                    l2=l2->next;
                }
                pre=pre->next;
            }
            if(l1){
                pre->next=l1;
            }
            if(l2){
                pre->next=l2;
            }
            return temp_head.next;
        }
       //合并k个
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0) return NULL;
            if(lists.size()==1) return lists[0];
            if(lists.size()==2) return mergeTwoLists(lists[0],lists[1]);
            int mid=lists.size()/2;
            vector<ListNode*> sub1_Lists;
            vector<ListNode*> sub2_Lists;
            for(int i=0;i<mid;i++){
                sub1_Lists.push_back(lists[i]);
            }
            for(int i=mid;i<lists.size();i++){
                sub2_Lists.push_back(lists[i]);
            }
            ListNode *l1=mergeKLists(sub1_Lists);
             ListNode *l2=mergeKLists(sub2_Lists);
            return mergeTwoLists(l1,l2);
        }
    };

     

    展开全文
  • 第一种:求出每一个链表的最小值,然后把这节点放到合并的结果链表里面,这个链表指向next 第二种:优先级队列,头结点放到优先级队列里面,将top的那一放到合并链表里面,再讲top指向next,push到队列里面 ...

    一、思路:

          第一种:求出每一个链表的最小值,然后把这个节点放到合并的结果链表里面,这个链表指向next

          第二种:优先级队列,头结点放到优先级队列里面,将top的那一个放到合并的链表里面,再讲top指向next,push到队列里面

    二、代码

         第一种思路:

    
    class Solution {
    public:
    	ListNode *insert(ListNode *nowNode, int val) {
    		if (nowNode == NULL)
    			return new ListNode(val);
    		else {
    			nowNode->next = new ListNode(val);
    			return nowNode->next;
    		}
    	}
    	ListNode* mergeKLists(vector<ListNode*>& lists) {
    		ListNode *res = NULL, *nowNode = res;
    		while (true) {
    			bool isAllNull = true;
    			int minVal = INT_MAX, pos = -1;
    			for (int i = 0; i < lists.size(); i++)
    			{
    				if (lists[i] != NULL) {
    					isAllNull = false;
    					if (lists[i]->val < minVal) {
    						pos = i;
    						minVal = lists[i]->val;
    					}
    				}
    
    			}
    			if (isAllNull)
    				return res;
    			lists[pos] = lists[pos]->next;
    			if (nowNode == NULL)
    				res = nowNode = insert(nowNode, minVal);
    			else
    				nowNode = insert(nowNode, minVal);
    		}
    		return res;
    	}
    };
    
    

     

         第二种思路:来源:https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/c-you-xian-dui-lie-liang-liang-he-bing-fen-zhi-he-/

    class Solution {
    public:
        // 小根堆的回调函数
        struct cmp{  
           bool operator()(ListNode *a,ListNode *b){
              return a->val > b->val;
           }
        };
    
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue<ListNode*, vector<ListNode*>, cmp> pri_queue;
            // 建立大小为k的小根堆
            for(auto elem : lists){
                if(elem) pri_queue.push(elem);
            }
            // 可以使用哑节点/哨兵节点
            ListNode dummy(-1);
            ListNode* p = &dummy;
            // 开始出队
            while(!pri_queue.empty()){
                ListNode* top = pri_queue.top(); pri_queue.pop();
                p->next = top; p = top;
                if(top->next) pri_queue.push(top->next);
            }
            return dummy.next;  
        }
    };

     

    展开全文
  • 将每个链表中元素放在一起,构造一元素数为k的小顶堆,每次取出堆顶元素,构成新的链表。 并把该元素后面的元素加入到堆中,反复操作直到堆为空。 使用优先队列来实现堆,可以方便运算。 代码实现 /** * ...

    题目描述

    这里写图片描述

    解题思路

    堆排序

    将每个链表中元素放在一起,构造一个元素个数为k的小顶堆,每次取出堆顶元素,构成新的链表。
    并把该元素后面的元素加入到堆中,反复操作直到堆为空。
    使用优先队列来实现堆,可以方便运算。

    代码实现

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    struct cmp
    {
        bool operator () (ListNode *a, ListNode *b)
        {
            return a->val > b->val;
        }
    };
    
    
    class Solution
    {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists)
        {
            priority_queue<ListNode*, vector<ListNode*>, cmp> que;
            for(int i = 0; i < lists.size(); i++)
            {
                if(lists[i])
                    que.push(lists[i]);
            }
            ListNode *head = NULL;
            ListNode *pre = NULL;
            ListNode *temp = NULL;
            while(!que.empty())
            {
                temp = que.top();
                que.pop();
                if(!pre) head = temp;
                else pre->next = temp;
                pre = temp;
                if(temp->next) que.push(temp->next);
            }
            return head;
        }
    };
    展开全文
  • 合并K个排序链表 题目 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 测试样例 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 ...
  • 合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 来源:力扣(LeetCode) 链接...
  • 思路1:按照21的思路,比较所有链表的值,最小的挂到新链表上,比较复杂,时间也很慢 排除 思路2:存到数组中,对数组排序,然后再重新链接 时间复杂度(kN*logkN) struct ListNode{ int val; ListNode * next...
  • 题目:合并k个排序链表,并且返回合并后的排序链表。样例给出3个排序链表[2-&gt;4-&gt;null,null,-1-&gt;null],返回 -1-&gt;2-&gt;4-&gt;null分析:采用归并排序的思想。数组的数递归划分...
  • 再将合并lists中所有的链表大问题,分解成“合并左部分的一半,再合并右边的一半,最后再进行一次合并”这样的小问题,并且这小问题还可以继续细分下去,直到变成只需要合并个链表,这样的步骤可以递归进行...
  • 23. 合并K个排序链表 - 力扣(LeetCode) 抓住链表本身有序这特点。 我们知道链表排序的主流算法是归并排序,而这题链表本身就有序,自然会联想到归并排序的merge函数:链表排序总结(全)(C++)_qq_32523711的...
  • 题目描述 此题难度等级为困难 ...C++题解 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class...
  • 对于合并k个有序链表,可以先看一下合并两有序链表的思想,(点这里) 对于k个链表的合并,我们可以基于两有序链表的合并思想,先将两个链表合并为一个链表,再将得到的结果链表与第三个链表合并为一个链表,...
  • 23.合并 k 个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6 ] 输出:1 -> 1 -> 2 -> 3 -> 4 ->...
  • 使用分治算法很容易解决 ListNode *merge(std::vector*>& lists,int s,int t){ if(s==t)return lists[s]...k个数列分治的时间复杂度为logk,而两有序数列进行排序的时间复杂度为n,所有时间复杂度为O(logk*n)
  • 合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ]输出: 1->1->2->3->4->4->5->6 ——题目难度:困难 ...
  • 简单来说就是不停的对半划分,比如k个链表先划分为合并个k/2个链表的任务,再不停的往下划分,直到划分成只有一或两个链表的任务,开始合并。举例子来说,比如合并6个链表,那么按照分治法,首先分别合并0和3,1...
  • 直接使用递归即可 ListNode *merge(std::vector&lt;ListNode*&gt;&amp; lists,int s,int t){ if(s==t)return lists[s]; int m=(s+t)/2; ListNode*l=merge(lists,s,m); ListNode*r=merge... ...
  • 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [  1->4->5,  1->3->4,  2->6 ] 输出: 1->1->2->3->4->4->5->6
  • 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入:[1->4->5,1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6 代码: /** * Definition ...
  • 合并k个排序链表 link 题目描述 合并\ k k 排序链表并将其作为一排序链表返回。分析并描述其复杂度。 题解: 分治+递归 每次将链表数组分为两等长的数组分别递归,将各自结果再用mergeTwo归并返回...
  • 目录(快速导航) 题目描述 视频讲解https://www.bilibili.com/video/av66438901/ 思路 代码 题目描述: ...合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4-&...
  • 题的思路和归并排序的思路一样。 归并的思想:递归地,或迭代地,将两已经... 传入两个链表的头结点,new一head节点当作合并后的链表的头结点,当两个链表都没有走到链尾的时候,将两链表的节点有序放入合并
  • 合并K个排序链表题目解答思路C++代码提交结果 题目 合并K个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3-&...
  • 本文首发于我的公众号码农之屋(id:Spider1818),专注于干货分享,包含...合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ]...
  • 该方法固然可行,但是是两两合并链表,时间复杂度O(nk)(n是链表个数,k链表长度)空间复杂度O(1)。显然,时间复杂度还不够低,应该优化。 node* mergeKLists(vector<node*>& lists) { if...
  • 合并 k 个排序链表,返回合并后的排序链表。 输入示例: [ 1->4->5, 1->3->4, 2->6 ] 输出示例: 1->1->2->3->4->4->5->6 本题是上题的升级版 合并有序链表 C++结构体: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,614
精华内容 3,445
关键字:

合并k个排序链表c++

c++ 订阅