LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

zhou_you 发布于2019-08-23 16:53 / 1904人阅读

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。

Time：2019/4/10
Title: Merge K Sorted Lists
Difficulty: Difficulty
Author: 小鹿

题目：Merge K Sorted Lists

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

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solve: ▉ 算法思路

如果我们完成了简单的基于两个单链表的合并之后，对于这个题来说，考察点是分治算法，我认为还有一个考察点就是递归调用，分治的同时经常用递归来解决。

1、本道题可以借助归并排序的思想，稍加改造就可以解决。

2、将数组中的链表分治，就是不断的将数组中的链表中间划分，分别合并，然后整体合并成一个大链表。

▉ 代码实现

/**
  * @param {number[]} nums
  * @return {number[]}
  * 功能：合并 k 个链表
  * 边界条件：
  * 1）判断数组是否为空
  * 2）判断数组长度为 1 时
  * 3）判断数组长度为 2 时
  * 4）判断数组长度大于 2 时
  */
var mergeKLists = function(lists) {
    // 当 lists 中有一个链表时
    if(lists.length == 0){
        return null;
    }else if(lists.length == 1){
        // 判断数组长度为 1 时
        return lists[0];
    }else if(lists.length == 2){
        // 判断数组长度为 2 时
        return mergeTwoLists(lists[0],lists[1]);
    }else{
        // 判断数组长度大于 2 时
        // 取数组的中部坐标
        let middle = Math.floor(lists.length/2);
        // 取左右两边数组
        let leftList = lists.slice(0,middle);
        let rightList = lists.slice(middle);
        // 递归、分割、合并
        return mergeTwoLists(mergeKLists(leftList),mergeKLists(rightList));
    }       
};
//两个链表合并
var mergeTwoLists = function(l1, l2) {
    let result = null;

    //终止条件
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //判断数值大小递归
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeTwoLists(l2.next,l1);
    }
    
    //返回结果
    return result;
};

▉ 扩展：分治算法

分治算法经常和递归一块使用，所谓分治算法，顾名思义，分而治之，最基本的分之算法在归并排序、快速排序都有用到。也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

1、分治算法递归每层操作

分解：将原问题分解成一系列的子问题。

解决：递归地求解各个子问题，若子问题足够小，则直接求解；

合并：将子问题的结果合并成原问题。

2、分治算法满足的条件

可分解：原问题与分解成的小问题具有相同的模式；

无关联：原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。

终止条件：具有分解终止条件；

合并不能太复杂：可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

混合云 idc机房托管合并链表的c语言第K顺序 kafka数据有序无序找出第k大的数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103456.html

LeetCode 之 JavaScript 解答第21题 —— 合并两个有序链表（Merge Two

摘要：什么意思呢比如上方合并链表的代码，分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿题目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
第7期 Datawhale 组队学习计划

马上就要开始啦这次共组织15个组队学习涵盖了AI领域从理论知识到动手实践的内容按照下面给出的最完备学习路线分类难度系数分为低、中、高三档可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 评论0 收藏0
PHPer也刷《剑指Offer》之链表

摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。温故知新链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。根据类型可以分为单链表、双链表、环形链表、...

daydream 2019-07-01 10:11 评论0 收藏0