Solution


Approach 1: Brute Force

Intuition & Algorithm

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

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

Complexity Analysis

  • Time complexity : where is the total number of nodes.

    • Collecting all the values costs time.
    • A stable sorting algorithm costs time.
    • Iterating for creating the linked list costs time.
  • Space complexity : .

    • Sorting cost space (depends on the algorithm you choose).
    • Creating a new linked list costs space.


Approach 2: Compare one by one

Algorithm

  • Compare every nodes (head of every linked list) and get the node with the smallest value.
  • Extend the final sorted linked list with the selected nodes.

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

Complexity Analysis

  • Time complexity : where is the number of linked lists.

    • Almost every selection of node in final linked costs ( times comparison).
    • There are nodes in the final linked list.
  • Space complexity :

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


Approach 3: Optimize Approach 2 by Priority Queue

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

  • Time complexity : where is the number of linked lists.

    • The comparison cost will be reduced to for every pop and insertion to priority queue. But finding the node with the smallest value just costs time.
    • There are nodes in the final linked list.
  • Space complexity :

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


Approach 4: Merge lists one by one

Algorithm

Convert merge lists problem to merge 2 lists () times. Here is the merge 2 lists problem page.

Complexity Analysis

  • Time complexity : where is the number of linked lists.

    • We can merge two sorted linked list in time where is the total number of nodes in two lists.
    • Sum up the merge process and we can get: .
  • Space complexity :

    • We can merge two sorted linked list in space.


Approach 5: Merge with Divide And Conquer

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

  • Pair up lists and merge each pair.

  • After the first pairing, lists are merged into lists with average length, then , and so on.

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

Thus, we'll traverse almost nodes per pairing and merging, and repeat this procedure about times.

Divide_and_Conquer

Complexity Analysis

  • Time complexity : where is the number of linked lists.

    • We can merge two sorted linked list in time where is the total number of nodes in two lists.
    • Sum up the merge process and we can get:
  • Space complexity :

    • We can merge two sorted linked lists in space.