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

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

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

/*
	采用递归的方法合并； -> 先合并两个 -> 递归迭代; -> 如果一个个递归迭代，时间复杂度是O(n^2)
		-> 采用并归排序；关键词：分治法
    ->要做到O(nlogn)的时间复杂度？ -> 采用并归排序
    //分治法：https://www.cnblogs.com/chengxiao/p/6194356.html；
    //https://cloud.baidu.com/article/3067219；最坏情况是O(n^2)
*/

func mergeKLists(lists []*ListNode) *ListNode {
	// write code here
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	if len(lists) == 2 {
		return merge2Lists(lists[0], lists[1])
	}
	mid := len(lists) / 2
	l1 := mergeKLists(lists[:mid])
	l2 := mergeKLists(lists[mid:])
	return merge2Lists(l1, l2)
}

func merge2Lists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	res := dummy
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			dummy.Next = l1
			l1 = l1.Next
		} else {
			dummy.Next = l2
			l2 = l2.Next
		}
		dummy = dummy.Next
	}
	if l1 == nil {
		dummy.Next = l2
	}
	if l2 == nil {
		dummy.Next = l1
	}
	return res.Next
}
//关键词：O(nlogn) -> 快排序；并归排序；分治法；递归；