算法--合并K个升序链表(Kotlin)

题目：

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

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

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方法：

1.使用优先队列合并

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    var priorityQueue = PriorityQueue<ListNode> { o1, o2 -> if (o1.`val` >= o2.`val`) 1 else -1 }
    for (list:ListNode? in lists) {
        if (list != null) {
            priorityQueue.add(list)
        }
    }
    var dump = ListNode(-1)
    var cur = dump
    while (!priorityQueue.isEmpty()){
        val poll = priorityQueue.poll()
        if (poll.next != null) {
            priorityQueue.add(poll.next)
        }
        cur.next = poll
        cur = cur.next
    }
    return dump.next
}

2.顺序合并

fun mergeTwoLists3(l1: ListNode?, l2: ListNode?): ListNode? {
    return if (l1 == null){
        l2
    }else if (l2 == null){
        l1
    }else if (l1.`val` > l2.`val`){
        l2.next = mergeTwoLists3(l1,l2.next)
        l2
    }else{
        l1.next = mergeTwoLists3(l1.next,l2)
        l1
    }
}
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    var result :ListNode? = null
    for (list in lists) {
        result = mergeTwoLists3(result,list)
    }
    return result
}

3.使用分治方法

fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    return mergeKMid(lists,0,lists.size-1)
}

fun mergeTwoLists3(l1: ListNode?, l2: ListNode?): ListNode? {
    return if (l1 == null){
        l2
    }else if (l2 == null){
        l1
    }else if (l1.`val` > l2.`val`){
        l2.next = mergeTwoLists3(l1,l2.next)
        l2
    }else{
        l1.next = mergeTwoLists3(l1.next,l2)
        l1
    }
}
fun mergeKMid(lists: Array<ListNode?>,left:Int,right:Int): ListNode? {
    if (left == right){
        return lists[left]
    }

    if(left > right){
        return null
    }

    var mid = (right + left) / 2
    return mergeTwoLists3(mergeKMid(lists,left,mid), mergeKMid(lists,mid+1,right))
}

参考题解：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/