LeetCode23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

有了上一个例子21的思路，这个题目就好做了，只需要设置一个头结点，然后三个互相比较不断的调整头结点的指向即可。 后面又想了想，这样做有点不太好实现，可以把每个list的节点push到同一个vector中，比较提取出最小的值，然后一一保存，最后链接这些值。

ListNode* mergeKLists(vector<ListNode*>& lists) 
{
	int len = lists.size();
	if (len ==1)
	{
		return lists[0];
	}
	if (len ==0)
	{
		return NULL;
	}
	vector<ListNode*> resultSet;
	for (int i=0;i<len;i++)
	{
		ListNode* head = lists[i];
		while (head!=NULL)
		{
			resultSet.push_back(head);
			head = head->next;
		}
	}
	std::sort(resultSet.begin(),resultSet.end(),cmp);
	resultSet.push_back(NULL);
	for (int j=0;j<resultSet.size()-1;j++)
	{
		resultSet[j]->next = resultSet[j + 1];
	}
	return resultSet[0];
}
bool cmp(const ListNode* a, const ListNode* b)
{
	if (a->val < b->val)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

写出来了，但是无法通过测试，会报错。 故直接看答案改写另一种方法。 答案使用分治归并的思想解答。 最终代码如下：

ListNode* mergeKLists(vector<ListNode*>& lists) 
{
	int len = lists.size();
	if (len == 0)
	{
		return NULL;
	}
	if (len == 1)
	{
		return lists[0];
	}
	if (len == 2)
	{
		return mergeTwoLists(lists[0], lists[1]);
	}
	int mid = len / 2;
	vector<ListNode*> sub1_lists;
	vector<ListNode*> sub2_lists;
	int i;
	for (i=0;i<mid;i++)
	{
		sub1_lists.push_back(lists[i]);
	}
	for (int j = i;j<len;j++)
	{
		sub2_lists.push_back(lists[j]);
	}
	ListNode* l1 = mergeKLists(sub1_lists);
	ListNode* l2 = mergeKLists(sub2_lists);
 
	return mergeTwoLists(l1, l2);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
	if (l1==NULL)
	{
		return l2;
	}
	if (l2 ==NULL)
	{
		return l1;
	}
	ListNode* p;
	ListNode* head = p;
	while (l1 !=NULL && l2 != NULL)
	{
		if (l1->val<l2->val)
		{
			head->next = l1;
			head = l1;
			l1 = l1->next;
		}
		else
		{
			head->next = l2;
			head = l2;
			l2 = l2->next;
		}
		if (l1==NULL)
		{
			head->next = l2;
		}
		if (l2 == NULL)
		{
			head->next = l1;
		}
	}
	return p;
}