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

package main


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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @return ListNode类
 */


func mergeKLists(lists []*ListNode) *ListNode {
    return devideMerge(lists,0,len(lists)-1)
}

func devideMerge (lists []*ListNode,left, right int) *ListNode {

    if left > right {
        return nil 
    }
    if left == right {
        return lists[left]
    }
    mid := (left + right)/2
    return Merge(devideMerge(lists,left,mid),devideMerge(lists,mid+1,right))

}
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {

	if pHead1 == nil {
		return pHead2
	}
	if pHead2 == nil {
		return pHead1
	}
	vh := &ListNode{}
	cur := vh
	for i := 0; ; i++ {
		if pHead1 == nil || pHead2 == nil {
			break
		}
		if pHead1.Val < pHead2.Val {
			cur.Next = pHead1
			pHead1 = pHead1.Next
		} else {
			cur.Next = pHead2
			pHead2 = pHead2.Next
		}
		cur = cur.Next
	}

	if pHead1 != nil {
		cur.Next = pHead1
	}

	if pHead2 != nil {
		cur.Next = pHead2
	}
	return vh.Next
}