23. Merge k Sorted Lists

1.问题

level：hard
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

来自 <https://leetcode.com/problems/merge-k-sorted-lists/> 

2.分析：

方法一：逐个链表合并
合并K个有序链表，之前做过合并两个有序链表的题，因此可以遍历数组一个一个合并
时间复杂度O(kN)
mergeTwoLists的时间复杂度是O(n),n是两个链表地 总长度，整个k链表合并过程需要

空间复杂度O(1)

方法二：
分治思想合并：
上面的方法每次都重复地遍历比较很多节点，优化地方法是，将k个链表先合并成k/2个，然后是k/4，k/8，….，1

时间复杂度:

空间复杂度：O(1)

3.C++代码：

//合并两个有序链表
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
	ListNode dummy(INT_MIN);
	ListNode *tail = &dummy;

	while (l1 && l2) {
		if (l1->val < l2->val) {
			tail->next = l1;
			l1 = l1->next;
		}
		else {
			tail->next = l2;
			l2 = l2->next;
		}
		tail = tail->next;
	}

	tail->next = l1 ? l1 : l2;
	return dummy.next;
}

//方法1：
ListNode* mergeKLists(vector<ListNode*>& lists)
{
	if (lists.empty())
		return nullptr;
	ListNode *front = lists[0];
	if (lists.size() == 1)
		return front;
	for (int i = 1; i < lists.size(); i++)
	{
		ListNode *tmp = mergeTwoLists(front, lists[i]);
		front = tmp;
	}
	return front;
}

//方法2：
ListNode* mergeKLists(vector<ListNode*>& lists)
{
	if (lists.empty())
		return nullptr;
	ListNode *front = lists[0];
	if (lists.size() == 1)
		return front;
	int Len = lists.size();
	int interval = 1;
	while (interval<Len)
	{
		for (int i = 0; i < Len- interval;i+= interval *2)
		{
			lists[i] = mergeTwoLists(lists[i], lists[i+ interval]);
		}
		interval *= 2;
	}
	return lists[0];
}

方法二需要注意地几点：
边界问题，i地取值i < Len- interval，保证lists[i+ interval]不越界