Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分支策略：每次归并两个已排好序的链表，直至只剩下一个链表。
public class Solution {public ListNode mergeKLists(List<ListNode> lists) {int length = lists.size();if (length == 0)return null;if (length == 1)return lists.get(0);ListNode low, high;while (length != 1){int index;for (index = 0; index < length/2; ++index){low = lists.get(2*index);high = lists.get(2*index+1);lists.set(index, merge2Lists(low, high));}if (length%2 == 1)lists.set(index, lists.get(length-1));length = (length + 1) / 2;}return lists.get(0);}public ListNode merge2Lists(ListNode low, ListNode high){ListNode result = new ListNode(-1);ListNode p = result;while (low != null && high != null){if (low.val < high.val){p.next = low;low = low.next;p = p.next;} else {p.next = high;high = high.next;p = p.next;}}if (low == null)p.next = high;elsep.next = low;return result.next;}}优先队列(或者说堆排序)：%E5%84%AA%E5%85%88%E4%BD%87%E5%88%97public class Solution {//此段代码出自https://oj.leetcode.com/discuss/25518/13-lines-in-java public ListNode mergeKLists(List<ListNode> lists) {Queue<ListNode> heap = new PriorityQueue(new Comparator<ListNode>(){@Override public int compare(ListNode l1, ListNode l2) {return l1.val – l2.val;}});ListNode head = new ListNode(0), tail = head;for (ListNode node : lists) if (node != null) heap.offer(node);while (!heap.isEmpty()) {tail.next = heap.poll();tail = tail.next;if (tail.next != null) heap.offer(tail.next);}return head.next;}}
，不是每一次努力都有收获，但是，每一次收获都必须经过努力。
