Merge k Sorted Lists Hard
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; Queue<ListNode> nodeList = new PriorityQueue<ListNode>(lists.length, (m, n) -> (m.val - n.val)); for (ListNode l : lists) { if (l != null) { nodeList.add(l); } } ListNode node = new ListNode(0); ListNode last = node; while (!nodeList.isEmpty()) { last.next = nodeList.poll(); last = last.next; if (last.next != null) nodeList.add(last.next); } return node.next; } 思路：利用PriorityQueue<T>排序能力，根据ListNode首元素值排序。首先把所有的链表全部加入Queue，这时poll就可以得到最小的元素（因原链表已经排序），将最小元素存入目标链表，并把当前链表去除首元素后入队，重复这个过程直到所有结点处理完毕。