题解 | #合并k个已排序的链表#

package main

func mergeKLists( lists []*ListNode ) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    }
    if n == 1 {
        return lists[0] // 递归终点1:
    }
    if n == 2 {
        return merge(lists[0], lists[1]) // 递归终点2：合并两条链表
    }
    tmp := n / 2
    return merge(mergeKLists(lists[:tmp]), mergeKLists(lists[tmp:])) //递归，数组拆两半
}

func merge(list1, list2 *ListNode) *ListNode {
    h := &ListNode{}
    ret := h
    for ;list1 != nil && list2 != nil; {
        if list1.Val < list2.Val {
            h.Next = list1
            list1 = list1.Next
        } else {
            h.Next = list2
            list2 = list2.Next
        }
        h = h.Next
    }
    if list1 == nil {
        h.Next = list2
    }
    if list2 == nil {
        h.Next = list1
    }
    return ret.Next
}