leetcode 23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

输入：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,vector<ListNode*>& lists)//区间是前闭后开{     //这道题并不会l>=r,但是如果传参失误则需要终止递归 看似多余实则不多余if(l>=r) return nullptr;if(r-l==1) return lists[l]; //表示当前区间只有一个元素lists[l] 有序直接返回即可int mid=(l+r)/2;            //确定中间值//返回排序后的左右分割链表return merge(apart_list(l,mid,lists),apart_list(mid,r,lists));}//合并lists[h]和lists[h1]链表ListNode* merge(ListNode* h,ListNode* h1){ListNode* temp=new ListNode(0);ListNode* l1=h;ListNode* l2=h1;ListNode* cur=temp;while(l1!=nullptr&&l2!=nullptr){if(l1->val>=l2->val){cur->next=l2;cur=cur->next;l2=l2->next;}else{cur->next=l1;cur=cur->next;l1=l1->next;}}cur->next=(l1==nullptr)? l2:l1;  Listnode* result=temp->next;delete temp;   //释放内存    return result;}ListNode* mergeKLists(vector<ListNode*>& lists) { int n=lists.size();if(n==0) return nullptr;       //链表数组为空返回nullptrif(n==1) return lists[0];      //链表数组为1直接返回lists[0]即可return apart_list(0,n,lists);  //返回分割的链表}
};