Two ideas to solve this problem.

1: Split the k sorted lists into 2 lists, until you reach 1 or 2 list, and then merge the two list (I did this before but I almost totally forgot, need recap.. T_T). Just like the merge sort.

Run time analysis:

T(k) = 2T(k/2)(split) + n*k(merge) according to master’s theorem, n is a constant to k, so case 2, and T(k) = nklogk. The space complexity is the run time stack, which is the hight of the split tree, and it is logk.

2: Maintain a priority queue (min heap) of size k. First we stick the first nodes of every list in to the heap. Then we remove the node from the heap top, and put the next node of the removed node into the heap to replace the removed one. This way we maintain a heap that contains the first node of the current list, and form the result list by removing the heap top.

Run time analysis:

To scan all the elements will take n*k time, and each element takes logk time to maintain the min-heap. So the total run time is also nklogk. The space complexity is the size of the heap, O(k)

method 1:

notice that we need only one pointer to merge 2 sorted list. Also notice the use of the subList(fromIndex(inclusive), toIndex(exclusive)). The subList API only works for list, so need to use the arrayList constructor.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists.size() == 0) return null; if (lists.size() == 1) return lists.get(0); if (lists.size() == 2) return merge(lists.get(0), lists.get(1)); // just like merge sort, split the list into half and recursive ListNode list1 = mergeKLists(new ArrayList<ListNode>(lists.subList(0, lists.size()/2))); ListNode list2 = mergeKLists(new ArrayList<ListNode>(lists.subList(lists.size()/2, lists.size()))); return merge(list1, list2); } public ListNode merge(ListNode n1, ListNode n2) {// merge two sorted list if (n1 == null) return n2; if (n2 == null) return n1; ListNode head = (n1.val < n2.val)?n1 : n2; // for return result ListNode tail = new ListNode(0); // helper for easy operation while(n1 != null && n2 != null) { if (n1.val < n2.val) { tail.next = n1; n1 = n1.next; } else { tail.next = n2; n2 = n2.next; } tail = tail.next; } if (n1 == null) // rest elements all from n2 tail.next = n2; if (n2 == null) // rest elements all from n1 tail.next = n1; return head; } }

method 2:

recap the use of the priority queue as min heap. treat the corner case of empty list and empty node as the list element

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { if (lists.size() == 0) return null; if (lists.size() == 1) return lists.get(0); PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){ // anonymous class, need to put init capacity as the first arg @Override public int compare(ListNode n1, ListNode n2) { if (n1.val > n2.val) return 1; if (n1.val < n2.val) return -1; return 0; } }); for (ListNode n : lists) { if (n != null) queue.add(n); } ListNode head = queue.peek(); ListNode tail = new ListNode(0); while(!queue.isEmpty()) { tail.next = queue.remove(); tail = tail.next; if (tail.next != null) queue.add(tail.next); } return head; } }