LeetCode题解-23 合并K个排序链表 Hard

时间:2022-01-16 11:02:13

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

答案:

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0)
return null;
return helper(lists, 0 , lists.length-1); } ListNode helper(ListNode[] lists, int l , int r){
//[l...r];
if(l == r)
return lists[l];
int mid = l+(r-l)/2;
ListNode left = helper(lists,l,mid);
ListNode right = helper(lists,mid+1,r);
return merge(left,right); } ListNode merge(ListNode left, ListNode right){
ListNode dummyHead = new ListNode(0),cur;
cur = dummyHead; while(left!=null || right!=null){
if(left != null && right !=null){
if(left.val<right.val){
cur.next=left;
cur=left;
left = left.next;
}
else{
cur.next=right;
cur=right;
right=right.next;
}
}else if(left==null){
cur.next=right;
cur=right;
right=right.next; }else if(right==null){
cur.next=left;
cur=left;
left = left.next; }
}
return dummyHead.next;
}
}