题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
桶排序YYDS
给的限制条件中，k和n都比较大，val大小被限制，时间限制比较严格，空间几乎无限，直接用空间换时间的方法，通过桶排序解决问题
第一步统计每个数值的个数，这里使用Map，统计很方便，还有自动排序的功能
ListNode *head, *temp, *cur;
head = nullptr;
map<int,int> m = {};
for (int i = 0;i < lists.size();i++){
for (temp = lists[i];temp != nullptr;temp=temp->next){
if (m.find(temp->val) != m.end()){
m[temp->val] += 1;
}
else{
m.insert(pair<int,int>(temp->val,1));
}
}
}
第二步处理下特殊情况
if (m.size() == 0){
return head;
}
第三步按照顺序新建ListNode输出就完事了，如果想要进一步提高性能，可以把while循环改成for循环便利map，这样就不用erase操作了
这里我新建了一个额外的节点避免在循环中给head赋值，减少判断的次数
head = new ListNode(100);
cur = head;
while(m.size() != 0){
int num = m.begin()->second,val = m.begin()->first;
for (int i = 0;i < num;i++){
temp = new ListNode(val);
cur->next = temp;
cur = temp；
}
m.erase(val);
}
head = head->next;
return head;
