package question;

import java.util.*;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question23 {
 public ListNode mergeKLists2(ListNode[] lists) {
 ListNode res = new ListNode(0);
 Queue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
 for (ListNode list : lists) {
 if (list != null) {
 queue.add(list);
 }
 }
 ListNode p = res;
 while (queue.size()>1) {
 p.next = queue.poll();
 p = p.next;
 if (p.next != null) {
 queue.add(p.next);
 }
 }
 p.next = queue.peek();
 return res.next;
 }


 public ListNode mergeKLists(ListNode[] lists) {
 ListNode res = new ListNode(0);
 Map<ListNode, Integer> map = new HashMap<>();
 Queue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
 for (int i = 0; i < lists.length; i++) {
 if (lists[i] != null) {
 map.put(lists[i], i);
 queue.add(lists[i]);
 }
 }
 ListNode p = res;
 while (queue.size()>1) {
 p.next = queue.poll();
 p = p.next;
 Integer index = map.remove(p);
 lists[index] = lists[index].next;
 if (lists[index] != null) {
 map.put(lists[index], index);
 queue.add(lists[index]);
 }
 }
 p.next = queue.peek();
 return res.next;
 }
}