Fusionar k listas enlazadas ordenadas y devolverlas como una lista ordenada. Analiza y describe su complejidad.
Análisis
La solución más simple es utilizar PriorityQueue. Los elementos de la cola de prioridad se ordenan según su orden natural, o mediante un comparador proporcionado en el momento de la construcción (en este caso).
Solución Java
public ListNode mergeKLists(ListNode[] lists) { if(lists==null||lists.length==0) return null; PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>(){ public int compare(ListNode l1, ListNode l2){ return l1.val - l2.val; } }); ListNode head = new ListNode(0); ListNode p = head; for(ListNode list: lists){ if(list!=null) queue.offer(list); } while(!queue.isEmpty()){ ListNode n = queue.poll(); p.next = n; p=p.next; if(n.next!=null) queue.offer(n.next); } return head.next; } |
Tiempo: log (k) * n.
k es el número de lista y n es el número de elementos totales.
Además, la definición del comparador de Java 8 se puede simplificar de la siguiente manera:
Comparator<ListNode> comp = Comparator.comparing(ListNode->ListNode.val); PriorityQueue<ListNode> queue = new PriorityQueue<>(comp); |
