23. 合并K个升序链表

解题思路：两种解法，一种优先级队列，一种分治

1. 优先级队列解法：以节点中存储的值进行排序

1. 依次遍历所有的链表，把链表中的节点加入到优先级队列中

2. 依次从优先级队列的弹出并删除最小的元素加入到新的链表中，直到队列为空，

3. 返回新的链表

AC代码：

class Solution {public static ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((first,second)->first.val-second.val);for (ListNode list : lists) {while (list!=null){queue.add(list);list=list.next;}}ListNode result = new ListNode();ListNode tem = result;while (queue.size()!=0){ListNode node =queue.remove();tem.next =node;tem=tem.next;}tem.next=null;//防止出现循环链，a->b->areturn result.next;}
}

2. 分治：类似与归并排序的思想

1. 如果链表的长度大于2：继续对链表进行拆分成两部分，继续使用分治的思想

1. 将链表数组数组分成两半，list[0,left]和list[left,end]，分别对这对两部分进行分治排序合并,这两部分排序后的结果first，second

2. 然后对first和second这两个链表进行双链表合并排序，合并思路：双指针：因为两个链表有序，所以只需要依次比较两个元素的大小，然后添加到新的链表中即可

1. first指针指向第一个链表，second指针指向第二个链表，result保存合并后的链表的头节点的前驱，tail初值指向result

2. 如果fist和second当前指向的节点都不为null，循环遍历：

1. 如果first.val<second.value，tail.next=first，first=first.next，tail=tail.next

2. 否则，tail.next=second，second=second.next，tail=tail.next

1. 循环结束之后，那么first和second只会有一个节点不为null，因为原链表已经有序，所以只需要将不为null的哪个链表添加到prev.next中即可

2. 最终result.next即为合并后链表的第一个节点

2. 如果链表的长度等于1：不需要分治合并，直接返回该链表即可

AC代码：

class Solution {public static ListNode mergeKLists(ListNode[] lists) {if (lists==null||lists.length==0){return null;}return merge(lists,0,lists.length-1);}//对list[left,right]范围的链表进行合并，返回合并后新的链表public static ListNode merge(ListNode[] lists,int left,int right){if (left==right){return lists[left];}int mid = (left+right)/2;ListNode first = merge(lists,left,mid);//对左半部的链表分进行分治合并，返回合并后的结果ListNode second = merge(lists,mid+1,right);//对右半部分的链表进行分治合并，返回合并后的结果ListNode result = sortMerge(first,second);//对first和second进行双链表合并return result;}public static ListNode sortMerge(ListNode first,ListNode second){ListNode result = new ListNode();ListNode tail = result;while (first!=null&&second!=null){if (first.val<second.val){tail.next= first;first=first.next;}else {tail.next=second;second=second.next;}tail = tail.next;}tail.next=(first==null)?second:first;return result.next;}
}