[路飞]_leetcode-23-合并K个升序链表

简介: leetcode-23-合并K个升序链表

网络异常,图片无法展示
|


「这是我参与11月更文挑战的第14天,活动详情查看:2021最后一次更文挑战


[题目地址][B站地址]


给你一个链表数组,每个链表都已经按升序排列。


请你将所有链表合并到一个升序链表中,返回合并后的链表。


示例 1:


输入: lists = [[1,4,5],[1,3,4],[2,6]]
输出: [1,1,2,3,4,4,5,6]
解释: 链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
复制代码


示例 2:


输入: lists = []
输出: []
复制代码


示例 3:


输入: lists = [[]]
输出: []
复制代码


提示:


  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4


本题我们可以首先想到一个最笨的方法


  1. 循环链表数组,找到当前所有链表中头节点最小的链表,拿到该节点
  2. 将该节点连接到结果链表末尾,并将对应链表指针向后移动一位
  3. 重复以上过程,知道链表数组中的每个链表都走到链表末尾


但是这个方法我们每次取到一个最小节点,就要循环一次链表数组,还要对比链表之间头节点的大小,效率是很低的,所以直接放弃掉


题解1


此题就是要每次找到值最小的节点,将它连接到结果链表的末尾,设计维护最值的情况,我们可以想到用堆来做

具体思路如下:


  1. 创建一个小顶堆
  2. 遍历链表数组,并将每一个节点 push 到小顶堆中
  3. 当堆不为空的时候,每次取出堆顶元素,组成新的链表


代码如下:


// 小顶堆实现
class MinHeap {
  constructor(){
    this.arr = [];
    this.size = 0;
  }
  push(node){
    this.arr.push(node);
    this.size++;
    if(this.size>1){
      let cur = this.size-1,
      parentInd = (cur-1)>>1;
      while(cur>0&&this.arr[parentInd].val>this.arr[cur].val){
        [this.arr[parentInd],this.arr[cur]] = 
        [this.arr[cur],this.arr[parentInd]];
        cur = parentInd,parentInd = (cur-1)>>1;
      }
    }
  }
  pop(){
    if(this.empty()) return false;
    const res = this.arr[0]
    this.arr[0] = this.arr.pop();
    this.size--;
    let cur = 0,
    childl = 1,
    childr = 2;
    while(
      (childl<this.size&&this.arr[childl].val<this.arr[cur].val)||
      (childr<this.size&&this.arr[childr].val<this.arr[cur].val)
    ){
      if(childr<this.size&&this.arr[childr].val<this.arr[childl].val){
        [this.arr[cur],this.arr[childr]] = 
        [this.arr[childr],this.arr[cur]];
        cur = childr;
      }else{
        [this.arr[cur],this.arr[childl]] = 
        [this.arr[childl],this.arr[cur]];
        cur = childl;
      }
      childl = cur*2+1,childr = cur*2+2;
    }
    return res;
  }
  empty(){
    return this.size === 0
  }
}
var mergeKLists = function(lists) {
  // 初始化小顶堆
  const heap = new MinHeap();
  // 将链表数组中的每个节点push到小顶堆中
  for(let i = 0;i<lists.length;i++){
    if(lists[i]===null) continue;
    while(lists[i]){
      heap.push(lists[i]);
      lists[i] = lists[i].next;
    }
  }
  const vhead = new ListNode(0);
  let cur = vhead;
  // 当堆不为空的时候,取出堆顶元素组成结果链表
  while(!heap.empty()){
    cur.next = heap.pop();
    cur = cur.next;
  }
  cur.next = null;
  return vhead.next;
};
复制代码


代码提交是可以通过的。但是用时 100ms 左右,只击败了 60% 左右的用户


题解2


本题其实可以用一种更为简单粗暴的方式来解


具体思路如下:


  1. 初始化一个空数组 arr
  2. 遍历链表数组,将链表的每一个节点的值 valpusharr
  3. arr 进行排序
  4. 根据排序后的 val 值生成结果链表


代码如下:


var mergeKLists = function(lists) {
  // 初始化数组
  const arr = [];
  // 遍历链表数组,将每个节点的值push到arr中
  for(let i = 0;i<lists.length;i++){
    if(lists[i]===null) continue;
    while(lists[i]){
      arr.push(lists[i].val);
      lists[i] = lists[i].next;
    }
  }
  // arr sort 排序
  arr.sort((a,b) => a-b)
  // 遍历arr,生成结果链表
  const vhead = new ListNode(0);
  let cur = vhead;
  for(let i = 0;i<arr.length;i++){
    cur.next = new ListNode(arr[i])
    cur = cur.next;
  }
  return vhead.next;
};
复制代码


代码提交通过后,用户 90ms 左右,击败了 90% 的用户


至此我们就完成了 leetcode-23-合并K个升序链表


如有任何问题或建议,欢迎留言讨论!

相关文章
|
3月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
46 1
|
3月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
59 0
Leetcode第21题(合并两个有序链表)
|
3月前
|
算法
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表
41 0
|
3月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
34 0
LeetCode第二十四题(两两交换链表中的节点)
|
3月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
50 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
3月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
112 0
|
3月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
28 0
|
4月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
5月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
68 6
|
5月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
137 2