golang 合并k个有序链表

可以使用分治法来解决这个问题。具体来说，我们可以将 k 个链表配对并将同一对中的链表合并。在第一轮合并之后， k 个链表被合并成了 k/2 个链表。重复这一过程，直到我们得到了最终的有序链表。

以下是 Golang 代码实现：

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    }
    for n > 1 {
        k := (n + 1) / 2
        for i := 0; i < n/2; i++ {
            lists[i] = mergeTwoLists(lists[i], lists[i+k])
        }
        n = k
    }
    return lists[0]
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }
    return dummy.Next
}

其中，`mergeTwoLists` 函数用于合并两个有序链表，`mergeKLists` 函数用于将 k 个有序链表合并成一个有序链表。时间复杂度为 O(Nlogk)，其中 N 是所有链表中的节点总数，k 是链表的数量。