23. Merge k Sorted Lists
1. Description
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.
2. Example
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: []
3. Constraints
- 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 won’t exceed $10^4$.
4. Solutions
My Accepted Solution
n = i_lists.size(), k is the number of nodes in each list
Time complexity: O($nklog_2n$)
Space complexity: O(n)
heap
class Solution
{
private:
struct Node
{
ListNode *node;
bool operator< (const Node &anotherNode) const
{
return node->val > anotherNode.node->val;
}
};
public:
// ListNode* mergeKLists(vector<ListNode*>& lists)
ListNode* mergeKLists(vector<ListNode*> &i_lists)
{
auto head = new ListNode();
priority_queue<Node> listsHeadValue;
for(auto node : i_lists)
{
if(node) listsHeadValue.push({node});
}
auto iter = head;
while(!listsHeadValue.empty())
{
auto node = listsHeadValue.top();
listsHeadValue.pop();
iter->next = node.node;
iter = iter->next;
if(node.node->next) listsHeadValue.push({node.node->next});
}
return head->next;
}
};
4.1 Divide and Conquer
n = i_lists.size(), k is the number of nodes in each list
Time complexity: O($nklog_2n$)
Space complexity: O($log_2n$)
class Solution
{
private:
ListNode* merge(ListNode *m_l1, ListNode *m_l2)
{
auto head = new ListNode();
auto iter = head;
while(m_l1 && m_l2)
{
iter->next = (m_l1->val < m_l2->val ? m_l1 : m_l2);
iter = iter->next;
m_l1->val < m_l2->val ? m_l1 = m_l1->next : m_l2 = m_l2->next;
}
iter->next = (m_l1 ? m_l1 : m_l2);
return head->next;
}
public:
ListNode* mergeKLists(vector<ListNode*> &m_lists)
{
if(m_lists.empty()) return nullptr;
vector<ListNode*> mergedLists;
while(m_lists.size() > 1)
{
for(int left = 0, right = m_lists.size() - 1; left <= right; left++, right--)
{
if(left == right) mergedLists.push_back(m_lists[left]);
else mergedLists.push_back(merge(m_lists[left], m_lists[right]));
}
swap(m_lists, mergedLists);
mergedLists.clear();
}
return m_lists.front();
}
};