题解 | #合并k个已排序的链表# go + 分治

go + 分治

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
*/
func mergeKLists(lists []*ListNode) *ListNode {
    if lists == nil || len(lists) == 0 {
        return nil
    }

    return merges(lists, 0, len(lists)-1)
}

// 分治
func merges(lists []*ListNode, start, end int) *ListNode {


    if start == end {
        return lists[start]
    }
    if start > end {
        return nil
    }

    mid := start + (end-start)/2
    left := merges(lists, start, mid)
    right := merges(lists, mid +1, end)

    return mergeDo(left, right)
}

// 合并两个链表
func mergeDo(l1, l2 *ListNode) *ListNode{
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    head := &ListNode{}
    node := head
    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            node.Next = l2
            l2 = l2.Next
        }else{
            node.Next = l1
            l1 = l1.Next
        }
        node = node.Next
    }

    if l1 != nil {
        node.Next = l1
    }
    if l2 != nil {
        node.Next = l2
    }

    return head.Next
}