Solution

Approach #1 Brute Force [Accepted]

Intuition & Algorithm

\n
• Traverse all the linked lists and collect the values of the nodes into an array.
\n
• Sort and iterate over this array to get the proper value of nodes.
\n
• Create a new sorted linked list and extend it with the new nodes.
\n

As for sorting, you can refer here for more about sorting algorithms.

Complexity Analysis

\n
• \n

  Time complexity : $$O(N\\log N)$$ where $$N$$ is the total number of nodes.

  \n
  \n
  • Collecting all the values costs $$O(N)$$ time.
  \n
  • A stable sorting algorithm costs $$O(N\\log N)$$ time.
  \n
  • Iterating for creating the linked list costs $$O(N)$$ time.
  \n
  \n
\n
• \n

  Space complexity : $$O(N)$$ .

  \n
  \n
  • Sorting cost $$O(N)$$ space (depends on the algorithm you choose).
  \n
  • Creating a new linked list costs $$O(N)$$ space.
  \n
  \n
\n

Approach #2 Compare one by one [Accepted]

Algorithm

\n
• Compare every $$\\text{k}$$ nodes (head of every linked list) and get the node with the smallest value.
\n
• Extend the final sorted linked list with the selected nodes.
\n

!?!../Documents/23_Merge_lists.json:1000,563!?!

Complexity Analysis

\n
• \n

  Time complexity : $$O(kN)$$ where $$\\text{k}$$ is the number of linked lists.

  \n
  \n
  • Almost every selection of node in final linked costs $$O(k)$$ ( $$\\text{k-1}$$ times comparison).
  \n
  • There are $$N$$ nodes in the final linked list.
  \n
  \n
\n
• \n

  Space complexity :

  \n
  \n
  • \n $$O(n)$$ Creating a new linked list costs $$O(n)$$ space.
  \n
  • \n $$O(1)$$ It\'s not hard to apply in-place method - connect selected nodes instead of creating new nodes to fill the new linked list.
  \n
  \n
\n

Approach #3 Optimize Approach 2 by Priority Queue [Accepted]

Algorithm

Almost the same as the one above but optimize the comparison process by priority queue. You can refer here for more information about it.

Complexity Analysis

\n
• \n

  Time complexity : $$O(N\\log k)$$ where $$\\text{k}$$ is the number of linked lists.

  \n
  \n
  • The comparison cost will be reduced to $$O(\\log k)$$ for every pop and insertion to priority queue. But finding the node with the smallest value just costs $$O(1)$$ time.
  \n
  • There are $$N$$ nodes in the final linked list.
  \n
  \n
\n
• \n

  Space complexity :

  \n
  \n
  • \n $$O(n)$$ Creating a new linked list costs $$O(n)$$ space.
  \n
  • \n $$O(k)$$ The code above present applies in-place method which cost $$O(1)$$ space. And the priority queue (often implemented with heaps) costs $$O(k)$$ space (it\'s far less than $$N$$ in most situations).
  \n
  \n
\n

Approach #4 Merge lists one by one [Accepted]

Algorithm

Convert merge $$\\text{k}$$ lists problem to merge 2 lists ( $$\\text{k-1}$$ ) times. Here is the merge 2 lists problem page.

Complexity Analysis

\n
• \n

  Time complexity : $$O(kN)$$ where $$\\text{k}$$ is the number of linked lists.

  \n
  \n
  • We can merge two sorted linked list in $$O(n)$$ time where $$n$$ is the total number of nodes in two lists.
  \n
  • Sum up the merge process and we can get: $$O(\\sum_{i=1}^{k-1} (i*(\\frac{N}{k}) + \\frac{N}{k})) = O(kN)$$ .
  \n
  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n
  \n
  • We can merge two sorted linked list in $$O(1)$$ space.
  \n
  \n
\n

Approach #5 Merge with Divide And Conquer [Accepted]

Intuition & Algorithm

This approach walks alongside the one above but is improved a lot. We don\'t need to traverse most nodes many times repeatedly

\n
• \n

  Pair up $$\\text{k}$$ lists and merge each pair.

  \n
\n
• \n

  After the first pairing, $$\\text{k}$$ lists are merged into $$k/2$$ lists with average $$2N/k$$ length, then $$k/4$$ , $$k/8$$ and so on.

  \n
\n
• \n

  Repeat this procedure until we get the final sorted linked list.

  \n
\n

Thus, we\'ll traverse almost $$N$$ nodes per pairing and merging, and repeat this procedure about $$\\log_{2}{k}$$ times.

Complexity Analysis

\n
• \n

  Time complexity : $$O(N\\log k)$$ where $$\\text{k}$$ is the number of linked lists.

  \n
  \n
  • We can merge two sorted linked list in $$O(n)$$ time where $$n$$ is the total number of nodes in two lists.
  \n
  • Sum up the merge process and we can get: $$O\\big(\\sum_{i=1}^{log_{2}{k}}N \\big)= O(N\\log k)$$ \n
  \n
  \n
\n
• \n

  Space complexity : $$O(1)$$ \n

  \n
  \n
  • We can merge two sorted linked lists in $$O(1)$$ space.
  \n
  \n
\n

Analysis written by: @Hermann0