0023.合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/

方法一：分而治之

时间复杂度 $O(kn \times \log k)$，空间复杂度 $O(\log k)$，其中 $O(k)$ 表示链表的数目，$O(n)$ 表示平均链表长度。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	var merge func(left, right int) *ListNode
	merge = func(left, right int) *ListNode {
		if left > right {
			return nil
		}
		if left == right {
			return lists[left]
		}
		mid := (left + right) / 2
		l := merge(left, mid)
		r := merge(mid+1, right)
		return mergeTwoLists(l, r)
	}
	return merge(0, len(lists)-1)
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for ; l1 != nil && l2 != nil; p = p.Next {
		if l1.Val < l2.Val {
			p.Next, l1 = l1, l1.Next
		} else {
			p.Next, l2 = l2, l2.Next
		}
	}
	if l1 != nil {
		p.Next = l1
	} else {
		p.Next = l2
	}
	return dummy.Next
}