class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
public ListNode partitionAndMerge(int si, int ei, ListNode[] lists) {
// 1. base case
if(si > ei) {
return null;
}
if(si == ei) {
return lists[si];
}
int mid = si+(ei-si)/2;
// break and merge
ListNode l1 = partitionAndMerge(si, mid, lists);
ListNode l2 = partitionAndMerge(mid+1, ei, lists);
return mergeTwoLists(l1, l2);
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) {
return null;
}
int k = lists.length;
return partitionAndMerge(0, k-1, lists);
}
}
OUTPUT:
All test cases were true.
No comments:
Post a Comment