Merge K sorted list

Published 7 months ago, last updated 7 months ago

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

We are given a list of singly linked list (be careful when you are dealing with list node problem). Thus it's intuitive to come up with the idea that maintaining a list or similar data structure to store the temp head of each list. So the only problem we need to figure out is:

How can we select the node with smallest value in a set of node

Java has provide us a useful data structure which automaticly sorts items we add named PriorityQueue. Yet we still need to do some work to let program knos how to sort these ListNode when we put them in. Here is one of the constructor for PriorityQueue:

 public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

We can put a random number in initialCapacity while the key part is how we implement Comparator. Since we want to pick the node with smallest value, here comes the Comparator

private static class MyListNodeComparator implements Comparator<ListNode> {
    @Override
    public int compare(ListNode l1, ListNode l2) {
        return l1.val - l2.val;
    }
}

Once we have our own Comaprator, solving this problem can be really easy. We add all node into queue. And keep selecting node from is until queue becomes empty. The only subtle problem is take care of Null. Queue does not accept null as an argument, otherwise your program will fail due to NullPointerException. So check you input during both initialization and iteration

Here is the code for the problem:

    public ListNode mergeKLists(ListNode[] lists) {
        Comparator<ListNode> comparator = new MyListNodeComparator();
        PriorityQueue<ListNode> queue = new PriorityQueue<>(5, comparator);
        ListNode record = null;
        ListNode newHead = record;
        for (ListNode listNode : lists) {
            if (listNode != null) {
                queue.offer(listNode);
            }
        }
        while (!queue.isEmpty()) {
            ListNode l = queue.poll();
            if (l == null) {
                continue;
            }
            if (newHead == null) {
                newHead = l;
                record = newHead;
            } else {
                newHead.next = l;
                newHead = newHead.next;
            }
            l = l.next;
            if (l != null) {
                queue.offer(l);
            }
        }
        return record;
    }
    
    private static class MyListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode l1, ListNode l2) {
            return l1.val - l2.val;
        }
    }


Comments

    No comment yet



Leave your comment