k-way merge Java solution with size-k heap


  • 0
    J

    this should be standard solution for k-way merge

        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
            PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new XComparator());
            for (int i = 0; i < lists.length; i++) if (lists[i] != null) queue.offer(lists[i]);
            ListNode head = new ListNode(0);
            ListNode lastNode = head;
            while (!queue.isEmpty()) {
                ListNode node = queue.poll();
                lastNode.next = node;
                if (node.next != null) queue.offer(node.next);
                lastNode = node;
            }
            return head.next;
        }
        
        static class XComparator implements Comparator<ListNode> {
            public int compare(ListNode x1, ListNode x2) {
                if (x1.val == x2.val) return 0;
                else if (x1.val > x2.val) return 1;
                else return -1;
            }
        }
    

  • 0
    C

    simpler

    static class XComparator implements Comparator<ListNode> {
            public int compare(ListNode x1, ListNode x2) {
                return x1.val - x2.val;
            }
        }

Log in to reply
 

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