leetcode-合并K个升序列表

题目
给你一个链表数组，每个链表都已经按照升序排列，请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例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 = []
输出：[]

分析

1. 首先两个数组的合并在前面的篇章中(合并两个有序链表)有实现过，现在是k个有序链表，那么如何处理呢？
2. 问题变成需要将K个链表的合并转化成2个链表的合并，于是我们就有以下思路：
   遍历原链表数组，依次取出两个链表进行合并,将合并的结果放到第二个链表所在位置，然后继续遍历，直到所有链表均合并完成，最后返回原链表的最后一个链表就是目标链表。代码实现如下：

实现一

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    if len(lists) == 1 {
        return lists[0]
    }

    // [list[0], list[1], list[2]]
    // [list[0] ,list[01],list[2]]
    // [list[0], list[01], list[012]]
        // 顺序取出两个链表合并后赋给第二个链表下标对应的位置
    for i := 0; i < len(lists); i++ {
        if i+1 < len(lists) {
            lists[i+1] = merge2List(lists[i], lists[i+1])
        }
    }
    return lists[len(lists)-1]
}

func merge2List(list1 *ListNode, list2 *ListNode) *ListNode {
    // 从链表1中删除节点，将删除节点插入到链表2中
    l1 := list1
    l2 := list2

    var l3 = &ListNode{0, nil}

    // 当其中一个链表为空时结束

    tail := l3
    // 每一轮，总是将最小的值放到l3末尾,同时剔除该节点
    for l1 != nil && l2 != nil {
        v1 := l1.Val
        v2 := l2.Val

        if v1 <= v2 {
            tail.Next = &ListNode{v1, nil}

            p := l1.Next
            l1 = p
        } else {
            tail.Next = &ListNode{v2, nil}

            p := l2.Next
            l2 = p
        }

        tail = tail.Next
    }
    if l1 != nil {
        tail.Next = l1
    }
    if l2 != nil {
        tail.Next = l2
    }
    return l3.Next
}

提交测试

* 134/134 cases passed (1266 ms)
* Your runtime beats 5.06 % of golang submissions
* Your memory usage beats 5.02 % of golang submissions (415.5 MB)

测试通过，但是效率低，同时空间占用较大。接下来我们考虑优化。

优化
我们分析代码，可以看到，整个数组遍历过程中，每一次合并之后原链表数组的前一个链表和我们的返回值是没有关系的，于是我们考虑置空，更进一步的，每次我们取出一个链表然后进行合并，将合并后的链表继续进行合并，直到返回，这样，就减少了整个空间的占用，同时也减少了计算的过程。代码实现如下:

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    if len(lists) == 1 {
        return lists[0]
    }

    // [list[0], list[1], list[2]]
    // [list[0] ,list[01],list[2]]
    // [list[0], list[01], list[012]]
        // 初始节点我们需从范围最小值开始，避免出现负数时无法排序。
    var dummy = &ListNode{-10000, nil}
    for i := 0; i < len(lists); i++ {
        dummy = merge2List(dummy, lists[i])
    }
    return dummy.Next
}

提交测试：

134/134 cases passed (804 ms)
Your runtime beats 5.06 % of golang submissions
Your memory usage beats 5.02 % of golang submissions (7.3 MB)

还行，有了一定的优化。

实现二
前面篇章中，我们对归并算法有一定了解，正好可以应用到此题中，思路是一致的。代码实现如下：

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    if len(lists) == 1 {
        return lists[0]
    }

    left := mergeKLists(lists[:len(lists)/2])  // 合并左半部分
    right := mergeKLists(lists[len(lists)/2:]) // 合并右半部分
    return merge2List(left, right)             // 最后把左半和右半合并
}

整个过程是一个递归的过程，时间复杂度是O(n*logk).