23. Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example 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
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
C++ Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ListNode *mergeKLists(vector<ListNode *> &lists) {
set<ListNode *> heads;
vector<ListNode *> sorted;
ListNode *merged = new ListNode();
ListNode *mergedHead = merged;
for (auto list : lists) {
heads.insert(list);
}
while (heads.size() > 0) {
ListNode *currentHead = nullptr;
int minVal = INT_MAX;
for (auto head : heads) {
if (head != nullptr && head->val < minVal) {
minVal = head->val;
currentHead = head;
}
}
sorted.push_back(currentHead);
merged->next = currentHead;
merged = merged->next;
heads.erase(currentHead);
if (currentHead != nullptr &¤tHead->next != nullptr) {
heads.insert(currentHead->next);
}
}
return mergedHead->next;
}
