1 题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
2 思路
当时看到这个题目就想到的是归并排序。好吧，但是，具体代码写不出来。题目给的是数组：public ListNode mergeKLists(ListNode[] lists)，我就想，怎么归并排序，然后返回一个已经排好的，再进行递归。想破脑袋没想出来。
原来，可以赋值给一个ArrayList，然后，List还有一个牛逼的方法：lists.subLists(int i,int j)方法，前面的是包括，后面的是不包括，天然的用于分治策略啊。
看的别人代码链接：
https://leetcode.com/discuss/10012/a-solution-use-divide-and-conquer-algorithm-in-java
https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue
3 代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
private ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode head = new ListNode(0);
ListNode node = head; ListNode list1 = l1;
ListNode list2 = l2; while(list1 != null && list2 != null){
if(list1.val > list2.val){
node.next = list2;
list2 = list2.next;
}else{
node.next = list1;
list1 = list1.next;
}
node = node.next;
} /* connect the longer list */
if(list1 != null){
node.next = list1;
}
if(list2 != null){
node.next = list2;
} return head.next;
} public ListNode mergeKLists(List<ListNode> lists) {
if(lists.size()==0) return null;
if(lists.size()==1) return lists.get(0);
if(lists.size()==2) return mergeTwoLists(lists.get(0),lists.get(1)); ListNode node1 = mergeKLists(lists.subList(0,lists.size()/2));
ListNode node2 = mergeKLists(lists.subList(lists.size()/2,lists.size())); return mergeTwoLists(node1,node2);
} public ListNode mergeKLists(ListNode[] lists){
List<ListNode> list = new ArrayList<>();
for(ListNode node : lists){
list.add(node);
}
return mergeKLists(list);
} }
看别人的代码，发现还有一个更简洁的递归写法：
return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), mergeKLists(lists.subList(lists.size()/2, lists.size())));
感觉像是 调用一个递归，然后参数还是递归。*了，希望将来能培养出这种思路和写法来。