题意
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
将K个排好序的链表合并成一个
解法
和之前合并两个有序链表那题不同,那题用的是两个指针来分别记录两个链表中的位置,将小的那个插入新链表然后指针右移,有点像归并排序时用到的方法。这题如果用K个指针来记录的话,每次需要找出最小的那个值,比较麻烦,所以采用的优先队列,首先将所有链表的第一个值入队,然后每次将值最小的一个出队插入新链表里,再将这个元素的下一个元素入队。
class Solution
{
struct Node
{
int val;
ListNode * next = nullptr;
bool operator <(const Node & r) const
{
return val > r.val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
int count = lists.size();
priority_queue<Node> que;
for(int i = 0;i < lists.size();i ++)
{
Node temp;
if(lists[i])
{
temp.val = lists[i] -> val;
temp.next = lists[i] -> next;
que.push(temp);
}
}
ListNode * head = nullptr;
ListNode * cur = nullptr;
while(!que.empty())
{
ListNode * node = new ListNode(0);
Node poped = que.top();
que.pop();
node -> val = poped.val;
node -> next = poped.next;
if(poped.next)
{
Node temp;
temp.val = poped.next -> val;
temp.next = poped.next -> next;
que.push(temp);
}
if(head == nullptr)
{
head = node;
cur = node;
}
else
{
cur -> next = node;
cur = cur -> next;
}
}
return head;
}
};