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

package main


/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @return ListNode类
 */
func mergeKLists( lists []*ListNode ) *ListNode {
    // write code here
    length := len(lists)
    if length == 0 {
        return nil
    }
    if length == 1 {
        return lists[0]
    }
    mid := length >> 1 // 分治
    return merge(mergeKLists(lists[:mid]), mergeKLists(lists[mid:])) // 归并

}

func merge(l1, l2 *ListNode) *ListNode {
    tmp := new(ListNode)
    ans := tmp
    // 合并
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            ans.Next = l1
            l1 = l1.Next
        }else {
            ans.Next = l2
            l2 = l2.Next
        }
        ans = ans.Next
    }
    if l1 != nil {
        ans.Next = l1
    }
    if l2 != nil {
        ans.Next = l2
    }
    return tmp.Next
}