23 合并 K 个升序链表

题目描述#

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

思路#

K 条链表一起排队？咱用分治抢先一步～

最最直觉的写法是：拿第 1 条和第 2 条 merge，再拿结果跟第 3 条 merge……一路串糖葫芦下来。可这么干每多合并一条就要把已合好的长链表整条扫一遍，总复杂度会退化到 O(K²·N)，K 一大就慢得让人怀疑人生。

聪明做法是 两两归并 + 分治——和归并排序的"合"那一步同根同源：

把 lists 数组从中间一刀切开，左半递归合成一条有序链表，右半也合成一条。
然后只需要把这两条已经排好序的链表 merge 起来即可。
递归出口是 left == right，这时候就只剩一条链表，直接返回。

每一层归并把链表数量减半，递归层数 O(log K)；每一层所有链表总共要扫的节点数是 N。总复杂度 O(N·log K)——比串糖葫芦优雅不止一个数量级～

merge 函数本身就是经典两路有序链表合并：用一个 dummy 哑节点起头，cur 跟着走、谁小接谁，最后把剩下那条非空链表整个挂上去就完事啦。

思维边界#

中点 mid := left + (right-left)/2 是肌肉记忆——和上一题四叉树同款防溢出习惯，别图省事写 (left+right)/2。
merge 里不要新建节点！直接复用入参链表的节点，cur.Next = leftNode 是把指针接过来，O(1) 操作；如果你 cur.Next = &ListNode{Val: ...} 那就额外开了 N 个节点的内存，没必要。
末尾收尾一定要把剩下那条链表整段挂上去（cur.Next = rightNode），而不是只接最后一个节点——链表本身就是递归结构，挂一头就连了一整条。
边界 len(lists) == 0：直接返回 nil，否则 right = -1 会让 mergeList(0, -1) 取到非法下标。
这题还有别的写法（小顶堆维护 K 个表头，每次取最小），复杂度同样是 O(N·log K)。分治写法不需要导入容器、纯靠递归，更显刀法干净。

困难题靠分治拆软——这就是分而治之的浪漫嘛！

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    left, right := 0, len(lists)-1

    var mergeList func(left, right int) *ListNode
    mergeList = func(left, right int) *ListNode {
        if left == right {
            return lists[left]
        }
        mid := left + (right-left)/2
        leftNode := mergeList(left, mid)
        rightNode := mergeList(mid+1, right)
        return merge(leftNode, rightNode)
    }
    return mergeList(left, right)
}

func merge(leftNode, rightNode *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for leftNode != nil && rightNode != nil {
        if leftNode.Val < rightNode.Val {
            cur.Next = leftNode
            leftNode = leftNode.Next
        } else {
            cur.Next = rightNode
            rightNode = rightNode.Next
        }
        cur = cur.Next
    }
    if leftNode == nil {
        cur.Next = rightNode
    } else if rightNode == nil {
        cur.Next = leftNode
    }
    return dummy.Next
}