# 2 simple Java solutions based merge sort idea

• For those who doesn't know about bottom-up merge sort, see this tutor link
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html

For Bottom-up iterative merge sort solution, I use a queue to maintain the merged result. It takes log(ListNode[].length) times to finish the merging part. Total it takes n*log(ListNode[].length) where n is the total number of nodes of ListNode[]
This solution can be done in parallel when dealing with massive list nodes , the Queue will be Queue<Future<ListNode>> to hold the feedback from ExecutorService.submit(callable), where callable is the Java Callable class caliing mergeTwoLists(ListNode l1, ListNode l2)

Another solution is just a simple recursive merge sort.

``````//17ms solution beats 75%: Bottom-up iterative merge sort
public ListNode mergeKLists(ListNode[] lists) {
for(int i = 0; i< lists.length;i+=2)
return listQueue.poll();
}
//14ms solution beats 91%: Recursive merge sort
public ListNode mergeKLists(ListNode[] lists) {
return mergesort(lists, 0, lists.length - 1);
}

public ListNode mergesort(ListNode[] lists, int left, int right) {
if (left > right) return null;
else if (left == right) return lists[left];
else {
int mid = (left + right) / 2;
ListNode l1 = mergesort(lists, left, mid);
ListNode l2 = mergesort(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else if (l1.val > l2.val) {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 != null ? l1 : l2;