精华内容
下载资源
问答
  • 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 来源:力扣(LeetCode) 链接:...
  • 合并K个排序链表

    2020-12-22 05:20:02
    定义一个合并的函数,然后反复使用以达到快速合并的效果。 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def ...
  • //合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 // // 示例: // // 输入: //[ // 1->4->5, // 1->3->4, // 2->...//Java:合并K个排序链表 public class...
    //合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 
    //
    // 示例: 
    //
    // 输入:
    //[
    //  1->4->5,
    //  1->3->4,
    //  2->6
    //]
    //输出: 1->1->2->3->4->4->5->6 
    // Related Topics 堆 链表 分治算法
    
    package leetcode.editor.cn;
    
    //Java:合并K个排序链表
    public class P23MergeKSortedLists {
        public static void main(String[] args) {
            Solution solution = new P23MergeKSortedLists().new Solution();
            // TO TEST
            ListNode listNode1_1 = new ListNode(1);
            ListNode listNode1_2 = new ListNode(4);
            ListNode listNode1_3 = new ListNode(5);
            listNode1_1.next = listNode1_2;
            listNode1_2.next = listNode1_3;
            ListNode listNode2_1 = new ListNode(1);
            ListNode listNode2_2 = new ListNode(3);
            ListNode listNode2_3 = new ListNode(4);
            listNode2_1.next = listNode2_2;
            listNode2_2.next = listNode2_3;
            ListNode listNode3_1 = new ListNode(2);
            ListNode listNode3_2 = new ListNode(6);
            listNode3_1.next = listNode3_2;
            //
            System.out.println(solution.mergeKLists(new ListNode[]{listNode1_1, listNode2_1, listNode3_1}));
        }
        //leetcode submit region begin(Prohibit modification and deletion)
    
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         * int val;
         * ListNode next;
         * ListNode(int x) { val = x; }
         * }
         */
        class Solution {
            public ListNode mergeKLists(ListNode[] lists) {
                int length = lists.length;
                if (lists == null || length < 1) {
                    return null;
                } else if (length == 1) {
                    return lists[0];
                }
                ListNode result = null;
                ListNode min;
                ListNode pointResult = null;
                int pointX;
                while (true) {
                    min = null;
                    pointX = 0;
                    for (int x = 0; x < length; x++) {
                        if (lists[x] != null) {
                            if (min == null || (lists[x].val < min.val)) {
                                pointX = x;
                                min = lists[x];
                            }
                        }
                    }
                    if (min == null) {
                        break;
                    }
                    lists[pointX] = min.next;
                    if (result == null) {
                        result = new ListNode(min.val);
                        pointResult = result;
                    } else {
                        pointResult.next = new ListNode(min.val);
                        pointResult = pointResult.next;
                    }
                }
                return result;
            }
        }
    //leetcode submit region end(Prohibit modification and deletion)
    
    }
    
    展开全文
  • 合并k个排序链表

    2020-05-01 18:02:06
    力扣23:合并k个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 思路...

    力扣23:合并k个排序链表

    合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

    示例:
    输入:
    [
    1->4->5,
    1->3->4,
    2->6
    ]
    输出: 1->1->2->3->4->4->5->6

    思路

    这让我想起了上次腾讯的题,n个数组的topK问题。这个也可以用一个优先队列维护一个最小值,每次都在队列中弹出最小值加入链表,再将这个节点的next加入到优先队列。
    思路很简单,这边代码方面可以着重看一下java的优先队列PriorityQueue的使用

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
    
            if(lists == null) return null;
            if(lists.length == 0) return null;
    
            ListNode ans = new ListNode(0);
            ListNode p = ans;
    
            int len = lists.length;
    
            PriorityQueue<ListNode> minQueue = new PriorityQueue<>(new Comparator<ListNode>() {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    return o1.val - o2.val;
                }
            });
    
            for(int i=0;i<len;i++) {
                if(lists[i] != null) minQueue.add(lists[i]);
            }
    
            while(!minQueue.isEmpty()) {
                ListNode node = minQueue.poll();
                if(node.next != null) minQueue.add(node.next);
                p.next = node;
                p = p.next;
            }
    
            return ans.next;
        }
    }
    
    展开全文
  • 第一种:求出每一个链表的最小值,然后把这节点放到合并的结果链表里面,这个链表指向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;  
        }
    };

     

    展开全文
  • 用C语言实现合并K个由大到小的排列的链表 思路:首先创建k个链表,并对其进行排序。然后用merge_linklist函数合并链表。 #include<stdio.h> #include<stdlib.h>//后面用到了malloc函数与rand函数 #...

    用C语言实现合并K个由大到小的排列的链表

    思路:首先创建k个链表,并对其进行排序。然后用merge_linklist函数合并链表。

    合并思路:扫描每个链表(如果链表已空,则跳过)找到所有链表当前节点值中的最小值,存放在temp中,并将此链表移动到下一个节点。然后将temp中的值存放到新链表当前节点中,新链表移动到下一个节点。直到将所有链表扫描完毕。

    在这里插入图片描述

    linklist merge_linklist(linklist l[],int k)
    {
     linklist L=NULL;
     lnode *s,*r=NULL;
     int i=0;
     int temp=100;
     int daihao;
     while(panduan_linklist(l,k)==1)//用来判断是否所有的链表已空
     {
      for(i=0;i<=k;i++)//扫描每个链表
      {
       if(l[i]==NULL)//如果有链表为空,则跳过
        continue;
       if(temp>l[i]->data)
       {
        temp=l[i]->data;//将最小值赋给temp
        daihao=i;//用来存放最小值所在链表的代号
       }
      } 
      l[daihao]=l[daihao]->next;
      s=(lnode*)malloc(sizeof(lnode));//为新节点开辟一个空间
      s->data=temp;//将最小值赋给data
      if(L==NULL)
       L=s;
      else r->next=s;
      r=s;
      temp=100; 
     } 
     if(r)
      r->next=NULL;
     return L;
    }
    int panduan_linklist(linklist l[],int k)//用来判断是否所有的链表已空
    {
     for(int i=0;i<=k;i++)
      if(l[i]!=NULL) 
      return 1;//如果有链表非空,返回1
      
     return 0;//如果所有的链表都空,返回0
    }

    下面是主函数

    #include<stdio.h>
    #include<stdlib.h>//后面用到了malloc函数与rand函数
    #include<time.h>//用到time函数来获取种子
    #define MAXSIZE 10000//定义链表个数最多为10000,也即k最大为10000
    typedef struct lnode//定义一个节点类型的结构体
    {
     int data;//用于存放节点的数据
     struct lnode *next;//存放下一个节点的地址
    }lnode,*linklist;//给结构体起个别名,其中linklist为头结点类型
    
    void main()
    {
     linklist creat_linklist()//创建链表函数
     void paixu_linklist(linklist L)//定义排序函数,对链表进行排序
     void put_out(linklist L)//输出函数 
     linklist merge_linklist(linklist l[],int k)//定义合并k个链表的函数 
     srand(time(NULL));//取时间为种子
     puts("请输入链表个数");
     int i;
     scanf("%d",&i);
     linklist l[MAXSIZE];//用数组存放k个链表
     linklist L;//定义合并后的链表
     for(int j=0;j<=i-1;j++)
     {
      l[j]=creat_linklist();
      paixu_linklist(l[j]);//对链表进行排序
      printf("第%d个链表为\n",j+1);//输出链表
      put_out(l[j]);
      puts("");
     }
     puts("合并后的来链表为");
     L=merge_linklist(l,i-1);//对k个链表进行合并
     put_out(L);//输出链表
    }
    void put_out(linklist l)
    {
     linklist L=l;int i=1;
     while(L!=NULL)
     {
      printf("%3d",L->data);
      if(i%21==0)
       puts("");
      L=L->next;
      i++;
     }
    }
    
    linklist creat_linklist()//创建链表
    {
     
     linklist l=NULL;
     lnode *s,*r=NULL;
     int x;
     int i=rand()%5+15;
     x=rand()%101;
     for(int j=0;j<=i;j++)
     {
      s=(lnode*)malloc(sizeof(lnode));
      s->data=x;
      if(l==NULL)
       l=s;
      else r->next=s;
      r=s;
      x=rand()%101;
     }
     if(r)
      r->next=NULL;
     return l;
    }
    
    void paixu_linklist(linklist l)//对链表进行排序
    {
     linklist L=l;
     int temp;
     int i=0;
     
     while(L!=NULL)
     {
      l=L;l=l->next;
      while(l!=NULL)
      {
       if(L->data>l->data)
       {
        temp=L->data;
        L->data=l->data;
        l->data=temp;
       }
       l=l->next;
      }
      L=L->next;
     }
    }
    展开全文
  • 23. 合并K个排序链表 题目描述 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6...
  • 23.合并 k 个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6 ] 输出:1 -> 1 -> 2 -> 3 -> 4 ->...
  • LeetCode题目(Python实现):合并K个排序链表题目想法一:分治法算法实现执行结果复杂度分析暴力法算法实现执行结果复杂度分析分治法(官方)算法实现执行结果复杂度分析小结 题目 合并 k 个排序链表,返回合并后的...
  • 输入两单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 这是一道经常被各公司采用的面试题*----《剑指offer》
  • 合并K个排序链表 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 暴力解题 1...
  • 描述: //合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 package leetCoder;... * @description : 合并K个排序链表 * @create : 2020/06/11 08:49 */ public class LeetCode23 {
  • 合并 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 来源:力扣...
  • Java实现 LeetCode 23 合并K个排序链表

    万次阅读 多人点赞 2020-02-12 15:54:32
    23. 合并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 本题是上题的升级版 合并有序链表 C++结构体: ...
  • 合并K个排序链表(python) 合并 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 方法一:贪心算法、...
  • 23. 合并K个排序链表

    2018-08-22 10:44:59
    合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [  1-&gt;4-&gt;5,  1-&gt;3-&gt;4,  2-&gt;6 ] 输出: 1-&gt;1-&gt;2-&gt;3-&gt;4...
  • 合并K个排序链表 python3

    千次阅读 2018-06-14 21:32:20
    合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: ...
  • 23. 合并K个排序链表 合并k个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 ...
  • leetcode23. 合并K个排序链表

    千次阅读 2019-01-16 16:23:45
    合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1-&amp;amp;gt;4-&amp;amp;gt;5, 1-&amp;amp;gt;3-&amp;amp;gt;4, 2-&amp;amp;gt;6 ] 输出: 1-&amp;...
  • 合并k个排序链表   描述 笔记  数据  评测 合并k个排序链表,并且返回合并后的排序链表。尝试分析和描述其复杂度。 您在真实的面试中是否遇到过这题?  Yes 样例 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,809
精华内容 11,523
关键字:

合并k个排序链表