package amazon;

import entity.ListNode;

import java.util.Comparator;

import java.util.PriorityQueue;

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

*/

/**

* Created by anduo on 17-3-13.

*/

public class MergeKSortedLists {

public ListNode mergetKLists(ListNode[] lists) {

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

PriorityQueue<ListNode> queue = new PriorityQueue<>(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 head = dummy;

for (ListNode node : lists) {

if (node != null) {

queue.add(node);

}

}

while (!queue.isEmpty()) {

head.next = queue.poll();

head = head.next;

if (head.next != null) {

queue.add(head.next);

}

}

return dummy.next;

}

}