最后一遍-L23-Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
NOTE:迭代，分治，链表
import util.ListNode;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
public static void main(String[] args) {
ListNode[] lists = new ListNode[3];
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
lists[0] = head;
ListNode head1 = new ListNode(3);
head1.next = new ListNode(4);
head1.next.next = new ListNode(5);
head1.next.next.next = new ListNode(6);
head1.next.next.next.next = new ListNode(7);
lists[1] = head1;
ListNode head2 = new ListNode(3);
head2.next = new ListNode(4);
head2.next.next = new ListNode(5);
head2.next.next.next = new ListNode(6);
lists[2] = head2;
System.out.println(mergeKLists_iterator(lists));
}
public static ListNode mergeKLists_iterator(ListNode[] lists) {
return mergeKLists(lists, 0, lists.length - 1);
}
public static ListNode mergeKLists(ListNode[] lists, int from, int to) {
if (from > to || from >= lists.length || to >= lists.length) return null;
if (from == to && from < lists.length && to < lists.length) return lists[from];
int mid = from + (to - from) / 2;
ListNode left = mergeKLists(lists, from, mid);
ListNode right = mergeKLists(lists, mid + 1, to);
return mergeTwoList(left, right);
}
public static ListNode mergeTwoList(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoList(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoList(l1, l2.next);
return l2;
}
}
public static ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val)
return -1;
else if (o1.val == o2.val)
return 0;
else
return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (ListNode node : lists)
if (node != null)
queue.add(node);
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
if (tail.next != null)
queue.add(tail.next);
}
return dummy.next;
}
}
标准的答案，其实就是感慨，正确的答案，都比较的优雅，并且代码量都不会很长
class Soution{
public ListNode mergeKLists(ListNode[]lists){
if(lists==null||lists.length==0)return null;
if(lists.length==1)return lists[0];
return merge(lists,0,lists.length-1);
}
public static ListNode merge(ListNode[]listNodes,int from,int to){
if(from==to)return listNodes[from];
int mid=from+(to-from)/2;
return mergeTwoList(
merge(listNodes,from,mid),
merge(listNodes,mid+1,to));
}
public static ListNode mergeTwoList(ListNode l1,ListNode l2){
if(l1==null)return l2;
if(l2==null)return l1;
return l1.val<l2.val?
new ListNode(l1.val,mergeTwoList(l1.next,l2)):
new ListNode(l2.val,mergeTwoList(l1,l2.next));
}
public static ListNode mergeTwoList_2(ListNode l1,ListNode l2){
if(l1==null)return l2;
if(l2==null)return l1;
if(l1.val < l2.val){
l1.next = mergeTwoList_2(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoList_2(l1,l2.next);
return l2;
}
}
}