母婴网站源码 带采集,网站空间费用一年多少,怎么对自己做的网站进行加密,简述一下网站建设流程给你一个链表数组#xff0c;每个链表都已经按升序排列。
输入#xff1a;lists [[1,4,5],[1,3,4],[2,6]]
输出#xff1a;[1,1,2,3,4,4,5,6]
解释#xff1a;链表数组如下#xff1a;
[1-4-5,1-3-4,2-6
]
将它们合并到一个有序链表中得到。
1-…给你一个链表数组每个链表都已经按升序排列。
输入lists [[1,4,5],[1,3,4],[2,6]]
输出[1,1,2,3,4,4,5,6]
解释链表数组如下
[1-4-5,1-3-4,2-6
]
将它们合并到一个有序链表中得到。
1-1-2-3-4-4-5-6首先我们想到的是归并排序对链表数组不断进行分割然后合并分割的链表/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public://分左右递归不断分割链表ListNode* apart_list(int l,int r,vectorListNode* lists)//区间是前闭后开{ //这道题并不会lr,但是如果传参失误则需要终止递归 看似多余实则不多余if(lr) return nullptr;if(r-l1) return lists[l]; //表示当前区间只有一个元素lists[l] 有序直接返回即可int mid(lr)/2; //确定中间值//返回排序后的左右分割链表return merge(apart_list(l,mid,lists),apart_list(mid,r,lists));}//合并lists[h]和lists[h1]链表ListNode* merge(ListNode* h,ListNode* h1){ListNode* tempnew ListNode(0);ListNode* l1h;ListNode* l2h1;ListNode* curtemp;while(l1!nullptrl2!nullptr){if(l1-vall2-val){cur-nextl2;curcur-next;l2l2-next;}else{cur-nextl1;curcur-next;l1l1-next;}}cur-next(l1nullptr)? l2:l1; Listnode* resulttemp-next;delete temp; //释放内存 return result;}ListNode* mergeKLists(vectorListNode* lists) { int nlists.size();if(n0) return nullptr; //链表数组为空返回nullptrif(n1) return lists[0]; //链表数组为1直接返回lists[0]即可return apart_list(0,n,lists); //返回分割的链表}
};
