LeetCode - Merge k Sorted Lists | Darren's Blog

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

• Priority Heap

public ListNode mergeKLists(ArrayList<ListNode> lists) {

    if (lists == null || lists.isEmpty())   // Empty lists

            return null;

    int k = lists.size();

    // Use a heap (priority queue) to process

    PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(k, new Comparator<ListNode>() {

        @Override

        public int compare(ListNode n1, ListNode n2) {

            return n1.val-n2.val;

        }

    });

    // Put the first (smallest) node into the heap

    for (ListNode node : lists) {

        if (node != null)

            heap.offer(node);

    }

 

    ListNode head = new ListNode(0), tail = head;   // Use a header to avoid boundary check

    // Put the smallest in the heap to the resulting list,

    // and add its next node (if any) to the heap

    while (!heap.isEmpty()) {

        ListNode temp = heap.poll();

        tail.next = temp;

        tail = tail.next;

        if (temp.next != null)

            heap.offer(temp.next);

    }

 

    return head.next;

Read full article from LeetCode - Merge k Sorted Lists | Darren's Blog