Merge K Sorted Lists LeetCode

思路: 先写两个lists merge的case，然后两两进行merge

时间复杂度为 log（K)*M
K为List的个数， M为最大List的长度。

public ListNode mergeKLists(ArrayList<ListNode> lists) {
int last = lists.size()-1;
if (last < 0) return null;
while (last > 0){
int curr = 0;
while (curr<last){
lists.set(curr, mergeTwoSortedList(lists.get(curr++), lists.get(last--)));
}
}
return lists.get(0);
}
//Merge two sorted list
public ListNode mergeTwoSortedList(ListNode l1, ListNode l2){
ListNode temp = new ListNode(-1);
ListNode prev = temp;

while(l1!=null && l2!=null){
if (l1.val>l2.val) {
prev.next = l2;
l2 = l2.next;
} else {
prev.next = l1;
l1 = l1.next;
}
prev = prev.next;
}

if (l1!=null) prev.next = l1;
if (l2!=null) prev.next = l2;

return temp.next;
}