Merge k sorted linked lists

Problem

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

Example:

Input:

[

  1->4->5,

  1->3->4,

  2->6

]

Output: 1->1->2->3->4->4->5->6

Solution

brutal force solution is to traversal all the linked lists, create an array, sort the array, then create a new linked list.

The time cost is O(NlogN), space cost is O(N)

we can also put the first k nodes into a priority queue, then take one at a time, push the next into the queue until done.

import java.util.*;
class KLinkedListsMerge {
  public static Node merge(Node[] nodes) {
    Node kHead = new Node(-1, null);
    Node tail = kHead;
    PriorityQueue<Node> pq = new PriorityQueue<>((i, j) -> i.value - j.value);
    for(Node head : nodes)
      pq.add(head);
    while(!pq.isEmpty()) {
      Node head = pq.poll();
      if(head.next != null)
        pq.add(head.next);
      head.next = null;
      tail.next = head;
      tail = head;
    }
    return kHead;
  }
  private static class Node {
    int value;
    Node next;
    public Node(int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }
  public static void main(String...args) {
    Node[] nodes = new Node[3];
    //1->4->5
    nodes[0] = new Node(1, new Node(4, new Node(5, null)));
    nodes[1] = new Node(1, new Node(3, new Node(4, null)));
    nodes[2] = new Node(2, new Node(6, null));
    Node head = merge(nodes);
    head = head.next;
    while(head.next != null) {
      System.out.print(head.value + " -> ");
      head = head.next;
    }
    System.out.println("null");
  }
}

The time cost is bounded by the priority queue, the queue size is k after initialization, then add each element need logk time to restore the order. The total time cost is O(Nlogk). Space cost is the O(k) which is the priority queue size.