11-28 19:53 南昌大学 算法工程师 发布于江西
关注
合并k个已排序的链表
这道题要求合并 k 个已排序的链表为一个新的有序链表，用数组排序 + 重建链表
首先，遍历所有输入链表，将每个节点的数值收集到一个数组中。接着对数组进行排序，利用排序后的数组重新构建一个新的有序链表
以下是对应的代码解析：
class Solution {public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> a; // 存储所有链表节点的数值
// 遍历所有链表，收集节点值
for (auto node : lists) {
ListNode* p = node;
while (p != NULL) {
a.push_back(p->val);
p = p->next;
}
}
sort(a.begin(), a.end()); // 对数值进行排序
ListNode dummy(0); // 虚拟头节点，简化链表构建
ListNode* q = &dummy;
// 用排序后的数值重建有序链表
for (int val : a) {
q->next = new ListNode(val);
q = q->next;
}
return dummy.next; // 返回新链表的头节点
}};
该解法的时间复杂度为O(NlogN)，空间复杂度为O(N)。
首先，遍历所有输入链表，将每个节点的数值收集到一个数组中。接着对数组进行排序，利用排序后的数组重新构建一个新的有序链表
以下是对应的代码解析：
class Solution {public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> a; // 存储所有链表节点的数值
// 遍历所有链表，收集节点值
for (auto node : lists) {
ListNode* p = node;
while (p != NULL) {
a.push_back(p->val);
p = p->next;
}
}
sort(a.begin(), a.end()); // 对数值进行排序
ListNode dummy(0); // 虚拟头节点，简化链表构建
ListNode* q = &dummy;
// 用排序后的数值重建有序链表
for (int val : a) {
q->next = new ListNode(val);
q = q->next;
}
return dummy.next; // 返回新链表的头节点
}};
该解法的时间复杂度为O(NlogN)，空间复杂度为O(N)。
全部评论
相关推荐
平安产险科技中心工作强度 24人发布 点赞 评论 收藏
分享
