## 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. 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.