Merge K sorted lists into one big sorted list in ascending order.

Assumptions

  • ListOfLists is not null, and none of the lists is null.
  public ListNode merge(List<ListNode> listOfLists) {
    PriorityQueue<ListNode> pq = new PriorityQueue(1, new Comparator<ListNode>() {
      public int compare(ListNode a, ListNode b) {
        return a.value - b.value;
      }
    });
    for (ListNode head : listOfLists) {
      if (head == null) {
          continue;
      }    
      pq.offer(head);
    }
    ListNode prev = null, head = null;
    boolean isFirst = true;
    while (!pq.isEmpty()) {
      ListNode cur = pq.poll();
      if (isFirst) {
        prev = cur;
        head = cur;
        isFirst = false;
      } else {
        prev.next = cur;
        prev = cur;
      }
      if (cur.next != null) {
        pq.offer(cur.next);
      }
    }
    return head;
  }

results matching ""

    No results matching ""