题目
合并 K 个排序链表
问题:
合并 k 个排序链表, 返回合并后的排序链表. 请分析和描述算法的复杂度.
解题思路:
这里就需要用到分治法 . 简单来说就是不停的对半划分, 比如 k 个链表先划分为合并两个 k/2 个链表的任务, 再不停的往下划分, 直到划分成只有一个或两个链表的任务, 开始合并. 举个例子来说比如合并 6 个链表, 那么按照分治法, 我们首先分别合并 1 和 4,2 和 5,3 和 6. 这样下一次只需合并 3 个链表, 我们再合并 1 和 3, 最后和 2 合并就可以了.
示例:
输入:
- [
- 1->4->5,
- 1->3->4,
- 2->6
- ]
输出: 1->1->2->3->4->4->5->6
代码:
- /**
- public class SingNode {
- public var value : Int
- public var nextNode: SingNode?
- public init(value:Int) {
- self.value = value
- }
- }
- **/
- func merchageTotalList(_ list : [SingNode?]) -> SingNode? {
- guard list.count> 0 else {
- return nil
- }
- var left = 0
- var right = list.count - 1
- var lists = list
- while right> 0 {
- left = 0
- while left <right {
- lists[left] = merchgeTwoList(lists[left], lists[right])
- left = left + 1
- right = right - 1
- }
- }
- return lists[0]
- }
- func merchgeTwoList(_ l1:SingNode?, _ l2:SingNode?) -> SingNode? {
- if l1 == nil {
- return l2
- }
- if l2 == nil {
- return l1
- }
- let dummy = SingNode.init(value: 0)
- var tempNode = dummy
- var L1 = l1
- var L2 = l2
- while L1 != nil && L2 != nil {
- if L1!.value < L2!.value {
- tempNode.nextNode = L1
- L1 = L1?.nextNode
- } else {
- tempNode.nextNode = L2
- L2 = L2?.nextNode
- }
- tempNode = tempNode.nextNode!
- }
- tempNode.nextNode = L1 ?? L2
- return dummy.nextNode
- }
来源: http://www.jianshu.com/p/88536e718287