leetcode 23. Merge k Sorted Lists
用二叉堆来优化：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
PriorityQueue <ListNode> queue = new PriorityQueue<ListNode>(lists.length, (a,b) -> a.val - b.val);
for(ListNode e: lists){
if(e != null){
queue.add(e);
}
}
ListNode ptr = new ListNode(0);
ListNode head = ptr;
while(!queue.isEmpty()){
ptr.next = queue.poll();
ptr = ptr.next;
if(ptr.next != null){
queue.add(ptr.next);
}
}
return head.next;
}
}
用 divide and conquer：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0){
return null;
}
if(lists.length == 1){
return lists;
}
if(lists.length == 2){
return mergeSort(lists,lists);
}
int mid;
ListNode[] sublist1;
ListNode[] sublist2;
if(lists.length % 2 ==0){
mid = lists.length/2;
sublist1 = new ListNode;
sublist2 = new ListNode;
}
else{
mid = lists.length/2;
sublist1 = new ListNode;
sublist2 = new ListNode;
}
for(int i = 0 ; i< mid ; i++){
sublist1= lists;
}
int count = 0;
for(int i = mid ; i< lists.length ; i++){
sublist2 = lists;
count++;
}
ListNode l1 = mergeKLists(sublist1);
ListNode l2 = mergeKLists(sublist2);
return mergeSort(l1,l2);
}
private static ListNode mergeSort(ListNode l1, ListNode l2){
ListNode ptr = new ListNode(0);
ListNode head = ptr;
while(l1 != null || l2 != null){
if(l2 == null || (l1 != null && l2.val >= l1.val)){
ptr.next = l1;
l1 = l1.next;
ptr = ptr.next;
}
else if (l1 == null || (l2 != null && l1.val > l2.val)){
ptr.next = l2;
l2 = l2.next;
ptr = ptr.next;
}
}
return head.next;
}
}
页:
[1]