精华内容
下载资源
问答
  • 合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6 """ ''' 思考: 三种方法:暴力、分治、最小堆(优先队列) 暴力解法...
  • 合并k个有序链表

    千次阅读 2020-05-19 18:15:16
    文章目录题目描述分析代码 题目描述 leetcode链接:https://leetcode-cn.com/problems/merge-k-sorted-lists/ 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。...`K`:链表个数。 方法一:

    题目描述

    leetcode链接:https://leetcode-cn.com/problems/merge-k-sorted-lists/

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

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

    分析

    `N`:链表总结点数。
    `K`:链表个数。
    

    方法一:暴力解法,将所有链表的所有值存入数组中,快排排序,再将排序好的建立节点连接。
    时间复杂度O(NlogN)
    空间复杂度O(N)

    方法二:优先队列优化,我们需要维护当前每个链表没有被合并的元素的最前面一个,K 个链表就最多有 K 个满足这样条件的元素,每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。

    时间复杂度:O(NlogK)
    空间复杂度:O(K)

    方法三:分治合并,

    • 将 K 个链表配对并将同一对中的链表合并;
    • 第一轮合并以后,K 个链表被合并成了 k 2 \frac{k}{2} 2k 个链表,平均长度为 2 n k \frac{2n}{k} k2n ,然后是 k 4 \frac{k}{4} 4k 个链表 k 8 \frac{k}{8} 8k 个链表等等;
    • 重复这一过程,直到我们得到了最终的有序链表。

    在这里插入图片描述

    代码

    /*
    方法一:暴力解法。
    */
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeKLists(self, lists: List[ListNode]) -> ListNode:
            nums = []
            for node in lists:
                while node:
                    nums.append(node.val)
                    node = node.next
    
            nums.sort()
    
            pre = ListNode(-1)
    
            node = pre 
            for i in nums:
                node.next = ListNode(i)
                node = node.next
                
            return pre.next
    
    /*
    方法二:优先队列
    */
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeKLists(self, lists):
            import heapq
    
            heap, cur = [], [] #初始化优先队列,建立链表索引
    
            for index, node in enumerate(lists):
                if node:
                    heapq.heappush(heap, (node.val, index))
                cur.append(node)
    
            pre = ListNode(-1)
            node = pre
    
            while heap:
                val, index = heapq.heappop(heap)
                node.next = ListNode(val)
                node = node.next
    
                cur[index] = cur[index].next
                if cur[index]:
                    heapq.heappush(heap, (cur[index].val, index))
    
            return pre.next
    
    /*
    方法三:分治归并
    */
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def mergeKLists(self, lists):
            length = len(lists)
            if length==0:
                return None
    
            interval = 1
            while interval<length:
                for i in range(0, length-interval, interval*2):
                    lists[i] = self.Merge(lists[i], lists[i+interval])
                interval *= 2
    
            return lists[0]
    
        def Merge(self, pHead1, pHead2):
            if not pHead1:
                return pHead2
            if not pHead2:
                return pHead1
            
            pMergeHead = None
            
            if pHead1.val < pHead2.val:
                pMergeHead = pHead1
                pMergeHead.next = self.Merge(pHead1.next, pHead2)
            else:
                pMergeHead = pHead2
                pMergeHead.next = self.Merge(pHead1, pHead2.next)
                
            return pMergeHead
    
            
    
    
    展开全文
  • 对于合并k个有序链表,可以先看一下合并两个有序链表的思想,(点这里) 对于k链表的合并,我们可以基于两个有序链表的合并思想,先将两链表合并为一链表,再将得到的结果链表与第三链表合并为一链表,...

    对于合并k个有序链表,可以先看一下合并两个有序链表的思想,(点这里

    对于k个链表的合并,我们可以基于两个有序链表的合并思想,先将两个链表合并为一个链表,再将得到的结果链表与第三个链表合并为一个链表,以此类推,最终将k个链表合并为一个有序链表。

    本篇不在累述这种方法,对于k个有序链表,我们可以考虑优先队列,首先将所有链表入队,然后重载比较操作符,用于构建链表节点的小根堆,依次取出队首节点,得到的新的链表就是一个有序的链表。

    这里有两个点需要注意:

    1.我们优先队列中的是一个个链表,而每次队首最小值就是当前这个链表的头节点的值,我们获得该头节点,并让队首元素出队,此时,出队的是整个链表,因此我们需要判断当前最小节点的下一个节点是否为空,不为空则说明后面还有节点,我们需要把下一个节点重新入队,参与排序。比如[{1,5,6},{2,4}] 我们让第一个链表出队了,获得了最小的头节点(值为1的),但后面的5-6需要重新入队参与排序。

    2.优先队列默认为大根堆,且入队的类型是链表,已定义的排序函数不能满足需求,所以我们需要重载比较函数,虽然是链表类型,但我们每次只需要比较每个链表的当前头节点的值大小即可。

    参考代码阅读,很好理解,代码如下:

    struct com{
        bool operator()(ListNode* node1,ListNode* node2)
        {
            return node1->val>node2->val;
        }
    };
    class Solution {
    public:
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            ListNode* head=new ListNode(-1);
            ListNode* res=head;
            if(lists.size()==0) return nullptr;
            priority_queue<ListNode*,vector<ListNode*>,com>pq;
            for(ListNode* node:lists)
                if(node!=nullptr)
                    pq.push(node);
            while(!pq.empty())
            {
                ListNode* min=pq.top();
                head->next=min;
                head=min;
                pq.pop();
                if(min->next!=nullptr)
                    pq.push(min->next);
            }
            return res->next;
        }
    };

     

    展开全文
  • title: leetcode-23-合并k个有序链表 date: 2019-09-07 10:56:17 categories: leetcode tags: leetcode 合并k个有序链表 合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ ...

    title: leetcode-23-合并k个有序链表
    date: 2019-09-07 10:56:17
    categories:

    • leetcode
      tags:
    • leetcode

    合并k个有序链表

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

      示例:

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

      来源:力扣(LeetCode)
      链接:https://leetcode-cn.com/problems/merge-k-sorted-lists
      著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    • 解法一:分治,利用上一题的合并两个有序链表的方法,利用分治达到目的,不过左边和右边有三种情况:

      1. left=right-1:这时候right–,同时令left=0
      2. left=right-2 这时候right还是–,同时令left=0;
      3. 不是上面两个条件,证明不是上面的内容,即没有到链表遍历完成
      /**
       * Definition for singly-linked list.
       * public class ListNode {
       *     int val;
       *     ListNode next;
       *     ListNode(int x) { val = x; }
       * }
       */
      class Solution {
          public ListNode mergeKLists(ListNode[] lists) {
              if(lists.length==0)
                  return null;
              int left = 0;
              int right = lists.length-1;
              while (left<right){
                  lists[left] = mergeTwoLists(lists[left],lists[right]);
                  if (left==right-1){
                      left = 0;
                      right--;
                  }else if(left==right-2){
                      left = 0;
                      right--;
                  }else {
                      left++;
                      right--;
                  }
              }
              return lists[0];
          }
          public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
              ListNode l3 = new ListNode(0);
              ListNode l4 = l3;
              while(l1!=null&&l2!=null)
              {
                  if(l1.val>l2.val)
                  {
                      l3.next = l2;
                      l2 = l2.next;
                  }else{
                      l3.next = l1;
                      l1 = l1.next;
                  }
                  l3 = l3.next;
              }
              if(l1==null)
              {
                  l3.next = l2;
              }else{
                  l3.next = l1;
              }
              return l4.next;
          }
      }
      
    • 解法二:贪心算法:使用优先队列:还可以使用堆来进行,优先队列确实我没有想到的方法,因为优先队列可以自己建立比较方法,同时优先队列是可以优化成为堆的,使用优先队列就相当于这道题开挂了

      /**
       * 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 len = lists.length;
              if (len == 0) {
                  return null;
              }
              PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(len, Comparator.comparingInt(a -> a.val));
              ListNode dummyNode = new ListNode(-1);
              ListNode curNode = dummyNode;
              for (ListNode list : lists) {
                  if (list != null) {
                      // 这一步很关键,不能也没有必要将空对象添加到优先队列中
                      priorityQueue.add(list);
                  }
              }
              while (!priorityQueue.isEmpty()) {
                  // 优先队列非空才能出队
                  ListNode node = priorityQueue.poll();
                  // 当前节点的 next 指针指向出队元素
                  curNode.next = node;
                  // 当前指针向前移动一个元素,指向了刚刚出队的那个元素
                  curNode = curNode.next;
                  if (curNode.next != null) {
                      // 只有非空节点才能加入到优先队列中
                      priorityQueue.add(curNode.next);
                  }
              }
              return dummyNode.next;
          }
      }
      
    展开全文
  • 合并K个有序链表

    2019-05-22 22:11:44
    合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 C++代码如下: /** * ...

    题目描述:

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

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

    C++代码如下:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if (lists.empty()) return NULL;
            int n = lists.size();
            while (n>1){ 
                int k = (n+1)/2;
                for (int i = 0; i<n/2; ++i){
                lists[i] = mergeTwoLists(lists[i],lists[i+k]);
            }
                n = k;
        }
            return lists[0];
    }
         ListNode* mergeTwoLists( ListNode *l1, ListNode *l2){
             ListNode *temp = new ListNode(-1) ,*p = temp;
             while (l1 && l2){
                 if (l1->val < l2->val){
                     p->next = l1;
                     l1 = l1->next;
                 }
                 else{
                     p->next = l2;
                     l2 = l2->next;
                 }
                 p = p->next;
             }
             if (l1) p->next = l1;
             if (l2) p->next = l2;
             return temp->next ;
         }
    };
    
    展开全文
  • 题目:合并k个有序链表 合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 ...
  • 今天白天没课 自己还是早早的就过来了 上午刷了一道题之后 还是一如既往的看了一场我詹的比赛 下午上党课 晚上在实验室做应用数理统计的题目时 ...明天早上起来吃一梅干菜和鱼香肉丝的包子 对我来说就又是新...
  • 该方法固然可行,但是是两两合并链表,时间复杂度O(nk)(n是链表个数,k是链表长度)空间复杂度O(1)。显然,时间复杂度还不够低,应该优化。 node* mergeKLists(vector<node*>& lists) { if...
  • c++ 合并k个有序链表

    2020-03-21 18:13:05
    二分思想,每次让数组二分,直到数组长度为1,输出结果 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} ...
  • 该题是leetcode的困难题,方案一是和21题一样,先合并个链表合并后的链表再和下个链表继续合并,循环下去,这种方案的时间复杂度为O(k^2*n),k表示链表的个数,n表示每个链表的平均节点数。方案一在leetcode上...
  • 给你一链表数组,每链表都已经按升序排列。请你将所有链表合并到一升序链表中,...将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2: 输入:lists = [] 输出:[] 示例 3
  • leetcode23.合并K个有序链表

    千次阅读 2019-06-04 15:32:11
    https://leetcode.com/problems/merge-k-sorted-lists/discuss/10527/Difference-between-Priority-Queue-and-Heap-and-C%2B%2B-implementation (评论里的新加一节点的那个) 优先队列方法: class Solution { ...
  • 题目:合并k个有序链表 题目描述: 合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1-&gt;4-&gt;5, 1-&gt;3-&gt;4, 2-&gt;6 ] 输出: ...
  • 题目 给你一链表数组,每链表都已经按升序排列。 请你将所有链表合并到一升序链表中,返回合并...6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2: 输入:lists =
  • 思路很简单,把所有的数据先读到ArrayList中然后转到数组中,然后排序,然后构建新链表 代码: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ...
  • Q:合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6 # Definition for ...
  • 23.合并K个有序链表1. 题目描述2.代码如下 原题目连接 1. 题目描述 合并 k 排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1-&...
  • 经典算法——合并K个有序链表

    万次阅读 2016-06-01 21:46:57
    K个有序链表合并为一个有序链表 二、实现方法: 方法一:利用最小堆方法 用一大小为K的最小堆(用优先队列+自定义降序实现)(优先队列就是大顶堆,队头元素最大,自定义为降序后,就变成小顶堆,队头元素最小)...
  • 一、合并K个链表 将n已经有序链表,合并成一个链表,使之有序 【1】排序法实现,时间复杂度为O(KNlogKN) 【2】分治法实现,时间复杂度为O(KNlogK) #include&amp;lt;iostream &amp;gt; #include&...
  • 题目要求是将k个有序链表合并为一链表,时间复杂度限定为O(nlogk)。下面给出应用最小堆方法的两程序,最后再贴上利用分治递归法的代码,虽然时间复杂度不及堆方法,但思路相对简单好理解。 (1)最小堆方法1 用...
  • 23.合并k个有序链表

    2021-01-20 17:04:07
    //给你一链表数组,每链表都已经按升序排列。 // // 请你将所有链表合并到一升序链表中,返回合并后的链表。 // // // // 示例 1: ...//将它们合并到一个有序链表中得到。 //1->1->2-&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,358
精华内容 9,343
关键字:

合并k个有序链表