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