内容简介：原题地址：这道题的题目是合并k个有序的链表，标定难度为逻辑不复杂，合并k个有序链表，我想不出来怎么一次性合并k个链表，貌似也不是不可以，但是代码感觉有点乱。但是更简单的方法就是反正我们刚做过21题，所以我们知道怎么合并两个有序链表。我们就一次合并两个有序链表，最后合并完全部的链表。这道题我们提供暴力解法和分而治之两种解法。
原题地址： https://leetcode.com/problems/merge-k-sorted-lists/
这道题的题目是合并k个有序的链表，标定难度为 Hard ，详细需求：
合并k个有序的链表，返回一个新的有序链表。
例子:
Input:
1->4->5,
1->3->4,
2->6
Output:1->1->2->3->4->4->5->6
逻辑不复杂，合并k个有序链表，我想不出来怎么一次性合并k个链表，貌似也不是不可以，但是代码感觉有点乱。但是更简单的方法就是反正我们刚做过21题，所以我们知道怎么合并两个有序链表。我们就一次合并两个有序链表，最后合并完全部的链表。这道题我们提供暴力解法和分而治之两种解法。
暴力解法
思路很简单一个for循环一个一个链表的去合并。总共需要合并k-1次。代码里面直接调用了 21题的mergeTwoLists方法 ：
分而治之解法
分而治之怎么解这道题呢？其实大概一想就知道了，就是把问题分成两半，然后把子问题再分成两半，直到问题小到只剩两个链表，然后再返回一步一步合并结果。分析完了你会发现这个问题跟归并排序（Merge-Sort）的思路是一样的。所以，我们的解法就完全模仿了《算法导论》的归并 排序 的写法。那么复杂度也就是nlog(n).
代码地址： https://github.com/tinyfool/leetcode/tree/master/src/p0023
这道题是分而治之，如果你对分而治之算法本身不太熟悉，请参阅《算法导论》。《算法导论》一书在2.3.1章节介绍了Merge Sort（归并排序），在第4章“分而治之”介绍了4.1 the maximum-subarray problem（最大子数组问题），4.2 Strassen’s algorithm for matrix multiplication （Strassen的矩阵乘法算法）。
也请参阅我的文章《 LeetCode专题 分而治之 》，文章中实现了算法导论里面的这三个分而治之的问题的代码，以及LeetCode相关问题的一个列表。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
C++标准模板库编程实战
Ivor Horton / 郭小虎、程聪 / 2017-1
《C++标准模板库编程实战》介绍最新的C++14标准的API、库和扩展，以及如何将它们运用到C++14程序中。在书中，作者Ivor Horton 则阐述了什么是STL，以及如何将它们应用到程序中。我们将学习如何使用容器、迭代器，以及如何定义、创建和应用算法。此外，还将学习函数对象和适配器，以及它们的用法。 阅读完本书之后，你将能够了解如何扩展STL，如何定义自定义类型的C++组件，你还将能够......一起来看看 《C++标准模板库编程实战》 这本书的介绍吧!
