合并 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;
}
}