新蔡县住房和城乡建设局网站,网上营销型网站有哪些,网站推广的具体方法,网站开发高级工程师专业描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围#xff1a;节点总数 0 \le n \le 50000≤n≤5000#xff0c;每个节点的val满足 |val| 1000∣val∣1000
要求#xff1a;时间复杂度 O(nlogn)O(nlogn)
示例1
输入#xff1a;
[{1…
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围节点总数 0 \le n \le 50000≤n≤5000每个节点的val满足 |val| 1000∣val∣1000
要求时间复杂度 O(nlogn)O(nlogn)
示例1
输入
[{1,2,3},{4,5,6,7}]
返回值
{1,2,3,4,5,6,7}示例2
输入
[{1,2},{1,4,5},{6}]
返回值
{1,1,2,4,5,6}解题报告
区分于归并排序。归并排序是说给定一个无序数组给排序成有序数组。
这个是说给定K个有序链表要求合并成一个有序链表
当然本质的merge(h1, h2)函数没变都是把两个有序序列给合并成一个有序序列。
这题还有一种做法不过空间复杂度较高一些时间复杂度是一样的就是用优先队列来存K个链表的头结点然后排序这样子。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *mergeKLists(vectorListNode * lists) {return mergeList(lists, 0, lists.size()-1);}ListNode* mergeList(vectorListNode * lists, int l, int r) {if(l r) {return lists[l];}if(l r) {return nullptr;}int mid (lr)/2;return mer(mergeList(lists, l, mid), mergeList(lists, mid1, r));}ListNode* mer(ListNode* h1, ListNode* h2) {ListNode* head new ListNode(-1);ListNode* p head;while(h1 h2) {if(h1-val h2-val) {p-next h1;h1 h1-next;p p-next;} else {p-next h2;h2 h2-next;p p-next;}}if(h1) p-next h1;else p-next h2;return head-next;}
};
