Merge k sorted linked lists and return it as one sorted list.
Example :
1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9
will result in
1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20
Solution:
Time: O(nlogk) Space: O(k)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { public ListNode mergeKLists(ArrayList<ListNode> a) { ListNode dummy = new ListNode(0); ListNode p = dummy; PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){ @Override public int compare(ListNode A, ListNode B) { return Integer.compare(A.val, B.val); } }); for (ListNode node : a) { pq.add(node); } while (!pq.isEmpty()) { ListNode next = pq.poll(); p.next = next; p = p.next; if (next.next != null) { pq.add(next.next); } } return dummy.next; } }