My Simple JAVA solution with time O(nlogk)


  • 0
    E

    This is my simple java solution using minHeap.

    /**
     * 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) {
            // sanity check
            if (lists == null || lists.length == 0) {
                return null;
            }
            int k = lists.length;
            PriorityQueue<ListNode> minHeap = new PriorityQueue<>(k, new Comparator<ListNode>() {
                @Override
                public int compare(ListNode a, ListNode b) {
                    if (a.val == b.val) {
                        return 0;
                    }
                    return a.val > b.val ? 1 : -1;
                }
            });
            for (int i = 0; i < k; i++) {   // initialize
                if (lists[i] != null) {
                    minHeap.offer(lists[i]);
                }
            }
            ListNode result = new ListNode(0);
            ListNode cur = result;
            while (!minHeap.isEmpty()) {
                ListNode temp = minHeap.poll();
                cur.next = temp;
                if (temp.next != null) {
                    minHeap.offer(temp.next);
                }
                cur = cur.next;
            }
            return result.next;
        }
    }
    

Log in to reply
 

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