LeetCode_23: Merge k Sorted Lists - LeetCode

# 引言

题目链接：https://leetcode.com/problems/merge-k-sorted-lists/description/

合并 k 个已排序的链表并将其作为一个排序列表返回。分析并描述其复杂性。

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

直接借用 21 题 Merge Two Sorted Lists 的双链表合并借用归并排序的思想分治合并即可

时间复杂度 O(nlogn)

空间复杂度 O(1)

c++ 版本

	class Solution
	{
	public:
	ListNode mergeKLists(vector<ListNode > &lists)
	{
	int n = lists.size();
	if (0 == n)
	{
	return nullptr;
	}
	while (n > 1)
	{
	int mid = (n + 1) >> 1;
	for (int i = 0; i < (n >> 1); ++i)
	{
	lists[i] = mergeTwoLists(lists[i], lists[i + mid]);
	}
	n = mid;
	}
	return lists[0];
	}

	private:
	ListNode mergeTwoLists(ListNode l1, ListNode *l2)
	{
	ListNode *pRet = new ListNode(0);
	ListNode *curNode = pRet;
	while (nullptr != l1 && nullptr != l2)
	{
	if (l1->val < l2->val)
	{
	curNode->next = l1;
	l1 = l1->next;
	}
	else
	{
	curNode->next = l2;
	l2 = l2->next;
	}
	curNode = curNode->next;
	}
	curNode->next = nullptr == l1 ? l2 : l1;
	return pRet->next;
	}
	};

go 版本

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

	func mergeKLists(lists []ListNode) ListNode {
	n := len(lists)
	if 0 == n {
	return nil
	}
	for n > 1 {
	mid := (n + 1) >> 1
	for i := 0; i < (n >> 1); i++ {
	lists[i] = mergeTwoLists(lists[i], lists[i+mid])
	}
	n = mid
	}
	return lists[0]
	}