# Solution by Hermann0

• ### Approach #1 Brute Force [Accepted]

Intuition & Algorithm

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

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

Python

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
self.nodes = []

for l in lists:
while l:
self.nodes.append(l.val)
l = l.next

for x in sorted(self.nodes):
point.next = ListNode(x)
point = point.next



Complexity Analysis

• Time complexity : $O(N\log N)$ where N is the total number of nodes.
• Collecting all values costs $O(N)$ time.
• A stable sorting algorithm costs $O(N\log N)$ time.
• Iterating for creating linked list costs $O(N)$ time.
• Space complexity : $O(N)$.
• Sorting cost $O(N)$ space (depends on the algorithm you choose).
• Create a new linked list costs $O(N)$ space.

### Approach #2 Compare one by one [Accepted]

Algorithm

• Compare every k nodes (head of every linked list) and get the node with the smallest value.

• Extend the final sorted linked list with seleted nodes.

Complexity Analysis

• Time complexity : $O(kN)$ where k is the number of linked lists.

• Almost every selection of node in final linked costs $O(k)$ (k-1 times comparison).
• There're N nodes in the final linked list.
• Space complexity :
• $O(n)$ Create a new linked list costs $O(N)$ space.
• $O(1)$ It's not hard to apply in-place method: connect selected nodes instead of creating new nodes to fill new linked list.

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

Algorithm

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

Python

from Queue import PriorityQueue

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
q = PriorityQueue()
for l in lists:
if l:
q.put((l.val, l))
while not q.empty():
val, node = q.get()
point.next = ListNode(val)
point = point.next
node = node.next
if node:
q.put((node.val, node))


Complexity Analysis

• Time complexity : $O(N\log k)$ where k is the number of linked lists.
• The comparasion 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.
• There're N nodes in the final linked list.
• Space complexity :
• $O(n)$ Create a new linked list costs $O(N)$ space.
• $O(k)$ The code I 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 situation)

### Approach #4 Merge lists one by one [Accepted]

Algorithm

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

Complexity Analysis

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

### Approach #5 Merge with Divide And Conquer [Accepted]

Intuition & Algorithm

This approach walk alongside the one above but improved a lot. We don't need to traverse most nodes many times repeatly:

• Pair up k lists and merge each pair.
• After first pairing, k lists are merged into k/2 lists with average 2N/k length, then k/4, k/8 and so on.
• Repeat this procedure until we get the final sorted linked list.

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

Python

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else lists

def merge2Lists(self, l1, l2):
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l1
l1 = point.next.next
point = point.next
if not l1:
point.next=l2
else:
point.next=l1


Complexity Analysis

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

• Yeah... I prefer to use $math$ instead of $$math$$.
Besides, I'm not a English native speaker, so I'll appreciate if you indicate or correct my mistake in grammer.

• I want to insert some graph for explaination, but I was hesitate about the policy of copyright. Can I insert graph with the statement of source or I have to made it by myself with general software?

• @Hermann0 said in Solution by Hermann0:

I want to insert some graph for explaination, but I was hesitate about the policy of copyright. Can I insert graph with the statement of source or I have to made it by myself with general software?

Depends on what rights you have to the original graph.

What's the point of starting your point ahead of your head? Why not start with point = head as people usually do?

I'm unfamiliar about this kind of commercial use and I think LeedCode prefer that the author deal with this kind of problem himself. So I raise this question to seek for some past experience about it.
Yeah, I noticed that people usually write this kind of thing in "point = head ". That's concise and correct. However, a variable name in Python is a little different to one in compiled language: it's more likely to be a pointer.
Python is the first programming language I learned, so I think some novice might be puzzled about these kind of features like this. So I want to write my code in a more ambiguity-free way.

• @Hermann0 Your explanation doesn't make sense to me. What would be the "ambiguity" of starting with point = head?

• @StefanPochmann Thanks for your reply and sorry for my poor explanation. I didn't want to prove that point = head is ambiguity.
We need two variable here, one for record the head and one for iterating (head and point). point = head meet this need properly, because these two variable name point to the same node. Intuitively, some people may regard them as two individual nodes and the consequent procedure may be a little confusing. I write my code in this way for avoiding the topic copy in Python.
• @Hermann0 Do you mean they might regard them as two individual nodes because they think point = head makes a copy of the object instead of referencing the same object? If so, then wouldn't they have the same issue with the other places where you make similar assignments?
• @StefanPochmann Yes, it's somehow embarrassed, I used to write my code in a way without copy-like assignment but it's sloppy since I have to operate pointers by point.next.next.next. You're right and I have modified my code for concision and consistency. Besides I have made some animation and images for explaination, but it's pitty I can't show them here.