【LeetCode】86. Merge k Sorted Lists
题目描述(Hard)
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题目链接
https://leetcode.com/problems/merge-k-sorted-lists/description/
Example 1:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
算法分析
方法一:逐一合并;
方法二:分治两两合并;
提交代码:
/**
* 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 NULL;
int interval = 1, len = lists.size();
while (interval < len)
{
for (int i = 0; i < len - interval; i += 2 * interval)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
interval *= 2;
}
return lists[0];
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *dummpy = new ListNode(-1);
ListNode *p = dummpy;
for (; list1 && list2; dummpy = dummpy->next)
{
if (list1->val < list2->val) { dummpy->next = list1; list1 = list1->next; }
else { dummpy->next = list2; list2 = list2->next; }
}
dummpy->next = list1 != NULL ? list1 : list2;
return p->next;
}
};