描述

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

思路

借鉴Merge Two Sorted Lists的解决思路，对两个数组先进行排序，然后两两组合，排成一个序列。

将此视为一种迭代的分而治之的解决方案。

mergeTwoLists方法是一种递归的合并两个序列的方法

注意：

尽量不用erase方法，太耗时。

一些优化以避免vector.erase()

比如下述：

while(lists.size() > 1){lists.push_back(mergeTwoLists(lists[0], lists[1]));lists.erase(lists.begin());lists.erase(lists.begin());}return lists.front();

改为使用指针方法遍历vector，最后取vector.back()

最终解决方案：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.empty()){return nullptr;}if(lists.size() == 1) return lists[0];int i = 0;while(i < lists.size() - 1){lists.push_back(mergeTwoLists(lists[i], lists[i+1]));i += 2;}return lists.back();}ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == nullptr){return l2;}if(l2 == nullptr){return l1;}if(l1->val <= l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}} };

 

转载于:https://www.cnblogs.com/ygh1229/p/9718627.html

总结

以上是生活随笔为你收集整理的【LeetCode】【数组归并】Merge k Sorted Lists的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。