LeetCode: Merge k Sorted Lists

LeetCode: Merge k Sorted Lists

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class MergeKSortedLists {
  public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length < 1) {
      return null;
    }
    Queue<ListNode> queue = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);

    for (ListNode n : lists) {
      if (n != null) {
        queue.add(n);
      }
    }
    ListNode preHead = new ListNode(0);
    ListNode cursor = preHead;

    while (!queue.isEmpty()) {
      ListNode tmp = queue.poll();
      cursor.next = tmp;
      if (tmp.next != null) {
        queue.offer(tmp.next);
      }
      cursor = cursor.next;
    }

    return preHead.next;
  }
}