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

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

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
*/
func mergeKLists( lists []*ListNode ) *ListNode {
	return merge(lists, 0, len(lists)-1)
}

func merge(list []*ListNode, left, right int) *ListNode {
	if left == right {
		return list[left]
	}
	if left > right {
		return nil
	}
	mid := left + (right-left)/2
	return mergeTwoList(merge(list, left, mid), merge(list, mid+1, right))
}

func mergeTwoList(list1, list2 *ListNode) *ListNode {
	res := &ListNode{Val: 0}
	tmp := res
	for list1 != nil && list2 != nil {
		if list1.Val > list2.Val {
			tmp.Next = &ListNode{Val: list2.Val}
			tmp = tmp.Next
			list2 = list2.Next
		} else {
			tmp.Next = &ListNode{Val: list1.Val}
			tmp = tmp.Next
			list1 = list1.Next
		}
	}
	if list1 != nil {
		tmp.Next = list1
	}
	if list2 != nil {
		tmp.Next = list2
	}
	return res.Next
}