问题陈述
您有一个k链接列表lists的数组，每个链接列表都按顺序排序。
将所有链接列表合并到一个排序的链接列表中并返回。
从：https://leetcode.com/problems/merge-k-sorted-lists
提取的问题声明 示例1：
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
示例2：
Input: lists = []
Output: []
示例3：
Input: lists = [[]]
Output: []
约束：
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.
合并K分类列表问题的解决方案问题
方法1：蛮力
在以前的博客文章之一中，我们讨论了如何Sort a single Linked List。在此问题中，我们需要合并K排序的链接列表。
一个简单的解决方案是将所有K链接列表连接到一个列表（按任何顺序）。然后使用Sort List帖子中讨论的合并排序算法。这种方法的最差时间复杂性是 o（n * log（n）），其中n是所有k列表中存在的节点总数。这种方法效率低下，因为我们没有利用已经分类的列表。
让我们检查以下此方法的C ++片段：
ListNode* getLastNode(ListNode* head) {
ListNode* current = head;
ListNode* next = current->next;
while(next != NULL) {
current = next;
next = current->next;
}
return current;
}
// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
// connect all k sorted linked lists into one list
for(int i = 0; i < lists.size() - 1; i++) {
// fetch the last node
ListNode* last = getLastNode(lists[i]);
last->next = lists[i + 1];
}
// perform merge sort on list[0]
return sortList(lists[0]);
}
// merge sort the two list
ListNode* mergelist(ListNode *l1, ListNode *l2) {
ListNode *ptr = new ListNode(0);
ListNode *current = ptr;
while(l1 != NULL && l2 != NULL) {
if(l1->val <= l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}
if(l1 != NULL) {
current->next = l1;
l1 = l1->next;
}
if(l2 != NULL) {
current->next = l2;
l2 = l2->next;
}
return ptr->next;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode *temp = NULL;
ListNode *slow = head;
ListNode *fast = head;
// split the list into two halves
while(fast != NULL && fast->next != NULL) {
temp = slow;
slow = slow->next;
fast = fast->next->next;
}
temp->next = NULL;
// recursively call the sortList function for the two lists
ListNode* l1 = sortList(head);
ListNode* l2 = sortList(slow);
// merge list l1 and l2
return mergelist(l1, l2);
}
一次解决该问题的第二种蛮力方法是merging two sorted lists。我们将前两个列表列表[0] 与列表[1] 合并并存储结果。我们将结果与第三列表合并列表[2] 并重复该过程k -1次。
此方法相对容易。但是这种方法的时间复杂性为 o（n * k），其中n是要合并的元素的数量。
这种方法的C ++片段如下：
// Merge k sorted lists: main function
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
return mergeKSortedListsHelper(lists);
}
// Helper function to merge k sorted lists
ListNode* mergeKSortedListsHelper(vector<ListNode*>& lists) {
int size = lists.size();
// Traverse from the second list to last
for (int i = 1; i <= size; i++) {
while(true) {
ListNode head1 = lists[0], head2 = lists[i];
// if the list has ended
if(head1 == NULL) {
break;
}
if(head1->val >= head2->val) {
lists[i] = head2->next;
head2->next = head1;
lists[0] = head2;
} else {
// Traverse the first list
while (head1->next != NULL) {
// find the node in the first list which is just
// greater than second list current node
if (head1->next->val >= head2->val) {
lists[i] = head2->next;
head2->next = head1->next;
head1->next = head2;
break;
}
head1 = head1->next;
}
if(head1->next == NULL) {
lists[i] = head2->next;
head2->next = NULL;
head1->next = head2;
head1->next->next = NULL;
break;
}
}
}
}
return lists[0];
}
上述两种方法的时间复杂性非常高，因为我们没有利用排序列表。我们可以使用其他数据结构来优化方法：最小堆
方法2：使用最小堆
我们可以使用Min Heap优化上述方法。最小堆的根始终是最小的元素。
根据问题语句，所有链接列表均已排序。因此，列表的第一个要素将是最小的。我们将所有链接列表的第一个元素添加到一个分钟堆中。我们提取最小的元素，即最小堆的根。删除根部后，我们将根元素所属的列表的指针递增。此列表的下一个节点添加到最小堆中。我们继续删除根部，并继续将下一个节点从列表中添加到堆中，直到所有列表都被遍历，并且堆为空。
该算法也可以用于合并K排序的数组。算法的时间复杂性为 o（n * log（k））。其中n是所有列表中元素的数量，k是链接列表的数量。空间复杂性是 o（k），其中k是最小堆的大小。
让我们检查该方法的算法。
- priority_queue<ListNode*, vector<ListNode*>, compare> pq
- for int i = 0; i < k; i++
- if lists[i] != NULL
- pq.push(arr[i])
- if end
- for end
- if pq.empty()
- return NULL
- if end
- ListNode* result = new ListNode(0)
ListNode* last = dummp
- loop while !pq.empty()
- ListNode* current = pq.top()
pq.pop()
- last->next = current
last = last->next
- if current->next != NULL
pq.push(curr->next)
- if end
- while end
- return result->next
让我们检查C ++代码中的算法。
ListNode* mergeKSortedLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
int k = lists.size();
// Push the first nodes of all the k lists in priority_queue 'pq'
for (int i = 0; i < k; i++)
if (lists[i] != NULL)
pq.push(lists[i]);
if (pq.empty())
return NULL;
ListNode *result = new ListNode(0);
ListNode *last = result;
// Loop till 'pq' is not empty
while (!pq.empty()) {
// Get the top element of 'pq'
ListNode* current = pq.top();
pq.pop();
// Add the top element of 'pq' to the result list
last->next = current;
last = last->next;
// If the current next node is not NULL, add it to the priority queue
if (current->next != NULL) {
pq.push(curr->next);
}
}
// return the result
return result->next;
}
方法3：使用鸿沟和征服
使用Min Heap，我们将时间复杂性缩短为 o（n * log（k）），但是它需要 o（k） o（k）堆的额外空间。我们可以使用鸿沟和征服技术在恒定空间中解决这个问题。
正如我们的蛮力方法中提到的那样，我们知道如何merge two sorted lists。这个想法是使用 o（1）空间将K列表配对并在线性时间内合并。在第一次迭代后，左右2 * n的k/2列表。第二个周期之后，剩下K/4列表。我们重复该过程，直到剩下一个列表为止。
让我们先检查算法。
// function mergeKLists(vector<ListNode*>& lists)
- if lists.size() == 0
- return NULL
- if end
- return mergeKListsHelper(lists, lists.size() - 1)
// function mergeKListsHelper(vector<ListNode*>& lists, int last)
// Merge lists until one list is left
- loop while last != 0
- initilaize i = 0, j = last
- loop while i < j
// merge list i with list j
// store the merged result in list i
- lists[i] = mergeLists(lists[i], lists[j])
- increment i = i++
- decrement j = j--
- if i >= j
- last = j
- if end
- while end
- while end
- return lists[0]
// function mergeLists(ListNode* l1, ListNode* l2)
- set ListNode* head = NULL
- if l1 == NULL
- return l2
- else if l2 == NULL
- return l1
- if end
- if l1->val < l2->val
- set head = l1
- set l1 = l1->next
- else
- set head = l2
- set l2 = l2->next
- if end
- set ListNode* p = head
- loop while l1 && l2
- if l1->val < l2->val
- set p->next = l1
- set l1 = l1->next
- else
- set p->next = l2
- set l2 = l2->next
- if end
- set p = p->next
- while end
- if l1 != NULL
- p->next = l1
- else
- p->next = l2
- if end
- return head
上述方法的时间复杂性为 o（n * log（k）），空间复杂性为 o（1）。
。让我们在 c ++ ， golang 和 javascript 中查看我们的解决方案。
。C ++解决方案
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0) {
return NULL;
}
return mergeKListsHelper(lists, lists.size() - 1);
}
ListNode* mergeKListsHelper(vector<ListNode*>& lists, int last) {
// Merge lists until one list is left
while(last != 0) {
int i = 0, j = last;
while(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j]);
i++;
j--;
// update last when all pairs are merged
if(i >= j) {
last = j;
}
}
}
return lists[0];
}
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
ListNode* head = NULL;
// if any one of the two lists is empty
// return the other list.
if(l1 == NULL) {
return l2;
} else if(l2 == NULL) {
return l1;
}
// choose the head based on the smallest value of two lists.
if(l1->val < l2->val){
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
ListNode *p;
p = head;
while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if(l1 != NULL){
p->next = l1;
} else {
p->next = l2;
}
return head;
}
};
Golang解决方案
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil;
}
return mergeKListsHelper(lists, len(lists) - 1)
}
func mergeKListsHelper(lists []*ListNode, last int) *ListNode {
// Merge lists until one list is left
for last != 0 {
i, j := 0, last
for(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j])
i++;
j--;
// update last when all pairs are merged
if i >= j {
last = j
}
}
}
return lists[0]
}
func mergeLists(l1, l2 *ListNode) *ListNode {
var head *ListNode
head = nil
// if any one of the two lists is empty
// return the other list.
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
// choose the head based on the smallest value of the two lists.
if(l1.Val < l2.Val){
head = l1;
l1 = l1.Next;
} else {
head = l2;
l2 = l2.Next;
}
p := head
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
p.Next = l1
l1 = l1.Next
} else {
p.Next = l2
l2 = l2.Next
}
p = p.Next
}
if l1 != nil {
p.Next = l1
} else {
p.Next = l2
}
return head
}
JavaScript解决方案
var mergeKLists = function(lists) {
if(lists.length === 0) {
return null;
}
return mergeKListsHelper(lists, lists.length - 1);
};
var mergeKListsHelper = function(lists, last) {
// Merge lists until one list is left
while(last != 0) {
let i = 0, j = last;
while(i < j) {
// merge list i with list j
// store the merged result in list i
lists[i] = mergeLists(lists[i], lists[j]);
i++;
j--;
// update last when all pairs are merged
if(i >= j) {
last = j;
}
}
}
return lists[0];
};
var mergeLists = function(l1, l2) {
let head = null;
// if any one of the two lists is empty
// return the other list.
if(l1 == null) {
return l2;
} else if(l2 == null) {
return l1;
}
// choose the head based on the smallest value of the two lists.
if(l1.val < l2.val){
head = l1;
l1 = l1.next;
} else {
head = l2;
l2 = l2.next;
}
let p = head;
while(l1 && l2){
if(l1.val < l2.val){
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if(l1 != null){
p.next = l1;
} else {
p.next = l2;
}
return head;
};
让我们干燥运行算法以了解解决方案的工作原理。
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
// mergeKLists function
Step 1: if lists.size() == 0
3 == 0
false
Step 2: return mergeKListsHelper(lists, lists.size() - 1)
mergeKListsHelper(lists, 2)
// mergeKListsHelper
Step 3: loop while last != 0
2 != 0
true
i = 0
j = last
= 2
loop while i < j
0 < 2
true
lists[i] = mergeLists(lists[i], lists[j])
lists[0] = mergeLists(lists[0], lists[2])
= mergeLists([1, 4, 5], [2, 6])
// mergeLists([1, 4, 5], [2, 6])
Step 4: This function will merge the list and return
[1, 2, 4, 5, 6]
// mergeKListsHelper
Step 5: i++
i = 1
j--
j = 1
if i >= j
1 >= 1
true
last = j
last = 1
loop while i < j
1 < 1
false
// mergeKListsHelper
Step 6: loop while last != 0
1 != 0
true
i = 0
j = last
= 1
loop while i < j
0 < 1
true
lists[i] = mergeLists(lists[i], lists[j])
lists[0] = mergeLists(lists[0], lists[1])
= mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
// mergeLists([1, 2, 4, 5, 6], [1, 3, 4])
Step 7: This function will merge the list and return
[1, 1, 2, 3, 4, 4, 5, 6]
// mergeKListsHelper
Step 8: i++
i = 1
j--
j = 0
if i >= j
1 >= 0
true
last = j
last = 0
loop while i < j
1 < 0
false
Step 9: loop while last != 0
0 != 0
false
Step 10: return lists[0]
[1, 1, 2, 3, 4, 4, 5, 6]