题目

合并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
    }