问题描述：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析：基于二分法，将k个list分为两部分，这两部分再次分别进行二分法，合并
算法：
public ListNode mergeKLists(ListNode[] lists) { //k个sorted list合并为一个sorted list if(lists == null || lists.length == 0) return null; int len = lists.length; if(len == 1) return lists[0]; int mid = len / 2; ListNode[] list1 = new ListNode[mid] ; ListNode[] list2 = new ListNode[len - mid] ; for(int i = 0 ;i < mid ; i++) list1[i] = lists[i]; for(int j = mid ;j < len;j++) list2[j - mid] = lists[j]; ListNode l1 = mergeKLists(list1); //递归 ListNode l2 = mergeKLists(list2); return mergeTwoSortedList_1(l1,l2); //合并 } //两个链表链接 public static ListNode mergeTwoSortedList_1(ListNode l1,ListNode l2){ ListNode head = new ListNode(0); //创建一个头结点，最后还要删掉 ListNode p = head; while(l1 != null && l2 != null){ if(l1.val <= l2.val){ p.next = l1; l1 = l1.next; } else{ p.next = l2; l2 = l2.next; } p = p.next; } p.next = (l1 != null) ? l1 : l2; return head.next;// head的下一个节点是第一个数据结点 }
Merge K Sorted List（含Merge Two Sorted LIst） leetcode java
原文：http://www.cnblogs.com/mydesky2012/p/5045036.html