Reference: LeetCode EPI 10.1
Difficulty: Hard

My Post: JAVA SUMMARY of all solutions (B-F, minPQ, Divide-And-Conquer)

Problem

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

Example: 

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Analysis

Focus on the third and fifth solution.

Test Case:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 1
[[1,4,5],[1,3,4],[2,6]]
[1,2,4,4,5]
// 2
[[], [], []]
[]
// 3
[[1,2],[],[5]]
[1,2,5]
// 4
[[1,4,5],[2,4]]
[1,2,4,4,5]
// 5
[[1]]
[1]
// 6 ---- Be careful of this one
[]

Brute-Force

It is okay if $N$ is not too large.

  • Traverse all the linked lists and collect the values of the nodes into an array. - $O(N)$
  • Sort the array. - $O(N\log{N})$
  • Traverse the array and make the linked list. - $O(N)$

Time: $O(N\log{N})$ where $N$ is the total number of nodes.
Space: $O(N)$ since we need an array and a new linked list.

Compare One-By-One

(if $k$ is much less than $N$, $k$ is the number of lists)

Compare every $k$ nodes (head of every list) and get the smallest node.

Note:

  • Use minIdx to record the location and to check if the list is empty.
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
28
29
30
31
32
public ListNode mergeKLists(ListNode[] lists) {
  if (lists == null || lists.length == 0) {
    return null;
  }
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;

  while (true) {
    ListNode minNode = null;
    int minIdx = -1;
    
    // Iterate over lists
    for (int i = 0; i < lists.length; ++i) {
      ListNode currList = lists[i];
      if (currList == null) continue;
      if (minNode == null || currList.val < minNode.val) {
        minNode = currList;
        minIdx = i;
      }
    }
    // check if finished
    if (minNode == null) break;

    // link
    prev.next = minNode;
    prev = prev.next;

    // delete
    lists[minIdx] = minNode.next; // may be null
  }
  return dummy.next;
}

Time: $O(kN)$ where $k$ is the number of linked lists. 311 ms
Space: $O(N)$ creating a new linked list. Or $O(1)$ if we apply an in-place method. Connect selected nodes instead of creating new nodes.

Compare One-By-One (minPQ)

Use a minimum priority queue to store $k$ nodes. Pop the smallest node and offer its next node if it is not null.

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
28
29
30
31
32
33
// Compare One-By-One (PQ)
public ListNode mergeKLists(ListNode[] lists) {
  if (lists == null || lists.length == 0) {
    return null;
  }
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;

  PriorityQueue<ListNode> minPQ = new PriorityQueue<>((o1, o2) -> {
    return o1.val - o2.val;
  });

  // Init PQ
  for (int i = 0; i < lists.length; ++i) {
    if (lists[i] != null) {
      minPQ.offer(lists[i]);
    }
  }

  // Play with PQ
  while (minPQ.size() > 0) {
    ListNode curr = pq.poll();
    prev.next = curr;
    prev = prev.next; // update

    // you don't need to set curr.next as null since the last node is always be one of the last node of each list. Its next must be null.
    if (curr.next != null) {
      minPQ.offer(curr.next);
    }
  }
  
  return dummy.next;
}

Time: $O(N\log{k})$ 34 ms

  • Initializing the priority queue takes $O(k\log{k})$
  • Pop $N$ nodes from the priority queue takes $O(N\log{k})$

Space: $O(k)$ since priority queue stores $k$ nodes. $O(1)$ or $O(N)$ depends on the input $N$ and $k$ and whether we create a new linked list.

Merge Lists One-By-One

We need to merge $k$ lists by merging $(k-1)$ times.

Note:

  • mergeList(dummy.next, n) is thoughtful. At the beginning, dummy.next is null, but it does not matter.
  • Alternatively, we can use the first place of the array to store merged list.
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
28
29
public ListNode mergeKLists(ListNode[] lists) {
  if (lists == null || lists.length == 0) {
    return null;
  }
  // Use the 0-th list as a return list
  for (int i = 1; i < lists.length; ++i) {
    lists[0] = mergeList(lists[0], lists[i]);
  }

  return lists[0];
}

private ListNode mergeList(ListNode n1, ListNode n2) {
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;
  while (n1 != null && n2 != null) {
    if (n1.val < n2.val) {
      prev.next = n1;
      n1 = n1.next;
    } else {
      prev.next = n2;
      n2 = n2.next;
    }
    prev = prev.next;
  }
  prev.next = (n1 != null) ? n1 : n2;

  return dummy.next;
}

Time: $O(kN)$ 250 ms

  • Merge two sorted lists in $O(n)$ time where $n$ is the total number of nodes in two lists. (worst case)
  • To sum up we have: $O(\sum_{i=1}^{k-1}(i * \frac{N}{k} + \frac{N}{k}) = O(kN)$. (key: $n = \frac{N}{k}$)

Space: $O(1)$ since we merge in place.

Merge Lists with Divide And Conquer

In effect, we don’t need to traverse most nodes many times repeatedly. We can divide lists in half until there is only one list. Merge them one by one to get the final result. It’s similar to mergesort.

Note:

  • Recall of the left-leaning and right-leaning cases.
  • The base case is thoughtful. lo > hi actually won’t occur. And lists[lo] won’t change other elements on the other side.
  • lists.length == 0 condition is very important.
    • Input case: [].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// mergeDivideAndConquer - O(kN)
public ListNode mergeDivideAndConquer(ListNode[] lists) {
  if (lists == null || lists.length == 0) {
    return null;
  }
  return divideAndConquer(lists, 0, lists.length - 1);
}

private ListNode divideAndConquer(ListNode[] lists, int lo, int hi) {
  if (lo > hi) { // invalid
    return null;
  }
  if (lo == hi) { // size = 1
    return lists[lo];
  }
  int mid = lo + (hi - lo) / 2; // left-leaning
  ListNode left = divideAndConquer(lists, lo, mid);
  ListNode right = divideAndConquer(lists, mid + 1, hi);
  return mergeList(left, right);
}

private ListNode mergeList(ListNode n1, ListNode n2) { ... }

Time: $O(N\log{k})$ 2 ms
Space: $O(\log{k})$ if we use recursion (depth of the recursion tree).

Merge with Divide And Conquer