Problem:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Method 1:
MergeSort. This is a very typical implementation for MergeSort by using array.
Code for method 1:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return helper(lists, 0, lists.length-1); } public ListNode helper (ListNode[] lists, int l, int h){ if (l < h){ int mid = (l + h)/2; return merge(helper(lists, l, mid), helper(lists, mid+1, h)); } return lists[l]; } public ListNode merge(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(0); ListNode temp = dummy; while (l1 != null && l2 != null){ if (l1.val < l2.val){ temp.next = l1; temp = temp.next; l1 = l1.next; }else{ temp.next = l2; temp = temp.next; l2 = l2.next; } } if (l1 != null){ temp.next = l1; } if (l2 != null){ temp.next = l2; } return dummy.next; } }
Analysis for time complexity:
Suppose there are k lists, and there are n elements inside each list. The time complexity is O(nklogk).
Method 2:
Use heap. Suppose we have k lists, and for each list, there are at most n elements.
Maintain a list of k elements. And always remove the first element from the list. After removing an element, add the element after it to the heap.
Code for method 2:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10, new Comparator<ListNode>(){ public int compare (ListNode l1, ListNode l2){ return l1.val - l2.val; } }); for (int i = 0; i < lists.length; i++){ ListNode temp = lists[i]; if (temp != null){ heap.offer(temp); } } ListNode dummy = new ListNode(0); ListNode cur = dummy; while (heap.size() != 0){ ListNode n = heap.poll(); cur.next = n; cur = cur.next; if (n.next != null){ heap.offer(n.next); } } return dummy.next; } }
Analysis for time complexity:
We have to insert at most k*n nodes, and for each node to be in order in the heap, we need log(k) time (“Bottom Up Insertion”). So total time complexity is also knlog(k).