合并k个排序链表，并且返回合并后的排序链表。
样例 给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null
一.目的：合并k个排序链表，并且返回合并后的排序链表
二.思路：法1：分治的思想，先将 k/2 的搞定，在将2个list merge起来
代码如下：
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param lists: a list of ListNode * @return: The head of one sorted list. */ public ListNode mergeKLists(List<ListNode> lists) { if(lists.size() == 0){ return null; } return mergeHelper(lists,0,lists.size() - 1); } private ListNode mergeHelper(List<ListNode> lists, int start, int end){ if(start == end){ //return Lists.get(start); 大小写错误 return lists.get(start); } int mid = start + (end - start) / 2; ListNode left = mergeHelper(lists, start, mid); ListNode right = mergeHelper(lists, mid + 1, end); return mergeTwoList(left,right); } private ListNode mergeTwoList(ListNode head1,ListNode head2){ ListNode dummy = new ListNode(0); ListNode tail = dummy; while(head1 != null && head2 != null){ if(head1.val < head2.val){ tail.next = head1; tail = tail.next; // 不该忘记 head1 = head1.next; }else{ tail.next = head2; tail = tail.next; //不该忘记 head2 = head2.next; } } if(head1 == null){ tail.next = head2; }else{ tail.next = head1; } return dummy.next; } }
