PriorityQueue or heapsort in Java O(nlogn)


  • 1
    I

    It is as good as merging all lists into one and sorting it with any other logn sorting algorithm:

    /**
     * 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) {
            
            PriorityQueue<Integer> q = new PriorityQueue<Integer>();
            for(ListNode l : lists) {
                while(l != null) {
                    q.add(l.val);
                    l = l.next;
                }
            }
            
            ListNode head = null, tail = null;
            while(!q.isEmpty()) {
                if(null == head) {
                    head = new ListNode(q.poll());
                    tail = head;
                } else {
                    tail.next = new ListNode(q.poll());
                    tail = tail.next;
                }
            }
            
            return head;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.