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

package main
import . "nc_tools"

//归并排序法，时间: kn*logk  空间:logk
func mergeKLists( lists []*ListNode ) *ListNode {
    // write code here
    if len(lists) == 0 {
        return nil
    }
    return merge(lists, 0, len(lists)-1)
}

func merge(lists []*ListNode, start, end int) *ListNode {
    if start == end {
        return lists[start]
    }

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

    return mergeTwoList(left, right)
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    pre := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            pre.Next = l1
            l1 = l1.Next
        } else {
            pre.Next = l2
            l2 = l2.Next
        }
        pre = pre.Next
    }

    if l1 == nil {
        pre.Next = l2
    }
    if l2 == nil {
        pre.Next = l1
    }
    return dummy.Next
}