今天在对2个list进行排序后，顺便做了下对K个list排序。
想的思路大概是，先通过某种方法，让这K个list最终都变成两个两个的list进行排序，然后调用之两个list排序的方法。见[LeetCode OJ]- Merge 2 Sorted Lists
那么怎么做合适呢？想到了上上学期算法课上学的一个【归并排序】的东东。说起来当时还不太理解，但是觉得归并排序不就是把一大堆数据，先折半折半再折半（二叉二叉再二叉）一直到只剩下叶子节点，然后从叶子节点开始，相邻的节点进行两两排序，从底向上，一直到根节点。
伪代码是这样的：
形象一点理解归并排序，参考这个图
理解了归并排序的思想，代码就很好实现了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return partition(lists, 0, lists.length - 1);
}
public static ListNode partition(ListNode[] listnode,int h,int r){
if(h == r) return listnode[h];
else if(h < r){
int m = (h + r)/2;
ListNode l1 = partition(listnode, h, m);
ListNode l2 = partition(listnode, m + 1, r);
return mergeTwoLists(l1, l2);
}
else return null;
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val < l2.val)
{
l1.next = mergeTwoLists(l1.next , l2);
return l1;
}
else
{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
