LeetCode_23: Merge k Sorted Lists

# 引言

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

# 题目大意

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

• Example

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)

# AC代码

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]
}