BiruLyu
7/28/2017 - 12:04 AM

23. Merge k Sorted Lists(#).java

//This is a classic interview question. Another similar problem is "merge k sorted lists".

//This problem can be solved by using a heap. The time is O(nlog(n)).

//Given m arrays, the minimum elements of all arrays can form a heap. It takes O(log(m)) to insert an element to the heap and it takes O(1) to delete the minimum element.

class ArrayContainer implements Comparable<ArrayContainer> {
int[] arr;
int index;

public ArrayContainer(int[] arr, int index) {
this.arr = arr;
this.index = index;
}

@Override
public int compareTo(ArrayContainer o) {
return this.arr[this.index] - o.arr[o.index];
}
}
public class KSortedArray {
public static int[] mergeKSortedArray(int[][] arr) {
//PriorityQueue is heap in Java
PriorityQueue<ArrayContainer> queue = new PriorityQueue<ArrayContainer>();
int total=0;

//add arrays to heap
for (int i = 0; i < arr.length; i++) {
queue.add(new ArrayContainer(arr[i], 0));
total = total + arr[i].length;
}

int m=0;
int result[] = new int[total];

//while heap is not empty
while(!queue.isEmpty()){
ArrayContainer ac = queue.poll();
result[m++]=ac.arr[ac.index];

if(ac.index < ac.arr.length-1){
queue.add(new ArrayContainer(ac.arr, ac.index+1));
}
}

return result;
}

public static void main(String[] args) {
int[] arr1 = { 1, 3, 5, 7 };
int[] arr2 = { 2, 4, 6, 8 };
int[] arr3 = { 0, 9, 10, 11 };

int[] result = mergeKSortedArray(new int[][] { arr1, arr2, arr3 });
System.out.println(Arrays.toString(result));
}
}
/**
* 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) {
if(lists.length == 0)
return null;
return partition(0, lists.length - 1, lists);
}

public ListNode partition(int i, int j, ListNode[] lists){
if(i == j)
return lists[i];
ListNode l1 = partition(i, (i + j) / 2, lists);
ListNode l2 = partition((i + j) / 2 + 1, j, lists);
return merge(l1, l2);
}

public ListNode merge(ListNode l1, ListNode l2){
if(l1 == null)
return l2;
if(l2 == null)
return l1;
ListNode head = null;
if(l1.val < l2.val){
head = l1;
head.next = merge(l1.next, l2);
}else{
head = l2;
head.next = merge(l1, l2.next);
}
return head;
}

}
/**
* 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) {
if (lists.length==0) return null;
int start = 0;
int end = lists.length-1;
while(end>0){
start=0;
while(start<end){
lists[start]=merge2(lists[start],lists[end]);
start++;
end--;
} }
return lists[0];
}
private ListNode merge2(ListNode l1,ListNode l2){
ListNode newh = new ListNode(1);
ListNode p= newh;
ListNode p1=l1;
ListNode p2=l2;
while(p1!=null&&p2!=null){
if(p1.val<=p2.val){
p.next=p1;
p1=p1.next;
p=p.next;
}
else{
p.next=p2;
p2=p2.next;
p=p.next;
}
}
if(p1!=null){
p.next=p1;
}
if(p2!=null){
p.next=p2;
}
return newh.next;
}
}
/**
* 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) {
int len = lists.length;
if (len == 0) {
return null;
}
//        ListNode listNode = lists[0];
//        for (int i = 1; i < len; i++) {
//            if (lists[i] == null)
//                continue;
//            if (listNode == null) {
//                listNode = lists[i];
//                continue;
//            }
//            listNode = mergeTwoKLists(listNode, lists[i]);
//        }
return  mergeKLists(lists,0,len-1);
}
public static ListNode mergeKLists(ListNode[] lists, int l, int r) {
if (l > r)
return null;
if (r == l)
return lists[r];
if (r - l == 1) {
return mergeTwoKLists(lists[l], lists[r]);
}
int mid = (l + r) >> 1;
ListNode lNode = mergeKLists(lists, l, mid);
ListNode rNode = mergeKLists(lists, mid + 1, r);
return mergeTwoKLists(lNode, rNode);
}

public static ListNode mergeTwoKLists(ListNode left  ,ListNode right) {
if (right == null)
return left;
if (left==null)
return  right;
ListNode tmp,root;
if (left.val>=right.val){
tmp=right;
right=right.next;
}
else {
tmp=left;
left=left.next;
}
root=tmp;
while (left!=null&&right!=null){
if (left.val>right.val){
tmp.next=right;
right=right.next;
tmp=tmp.next;
}
else {
tmp.next=left;
left=left.next;
tmp=tmp.next;
}
}
if (left!=null)
tmp.next=left;
if (right!=null)
tmp.next=right;

return root;
}
}
/**
* 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) {

if( lists == null || lists.length == 0) return null;

PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
public int compare(ListNode n1, ListNode n2){
return n1.val - n2.val;
}
});

for(ListNode list:lists){
if(list != null)
q.offer(list);
}

ListNode head = new ListNode(-1);
ListNode temp = head;

while(!q.isEmpty()){
ListNode n = q.poll();
temp.next = n;
temp = temp.next;

if(n.next != null)
q.offer(n.next);
}

return head.next;

}
}