Can anyone please help solve this error? I have no idea why its wrong. I keep getting runtime error when doing "23. Merge k Sorted Lists", but my stdout is consistent with expectations.

```
Runtime Error
TypeError: [] is not valid value for the expected return type ListNode
raise TypeError(str(ret) + " is not valid value for the expected return type ListNode");
Line 65 in _driver (Solution.py)
_driver()
Line 71 in <module> (Solution.py)
```

Here is my code:

```
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists: return lists
if len(lists) == 1: return lists[0]
# return itself if 'lists' is empty or only has one ListNode
head = ListNode()
dummy_front = head
dummy_last = ListNode(10**5)
# During comparison, if a linkedlist is out of nodes, assign dummy_last to be its last node. The maximum value of a listnode is 10**4, so dummy_last would be the largest.*
flag = 0
# Use all_values to contain the current listnodes' values of all Linked lists. For example, with lists = [[1,4,5],[1,3,4],[2,6]], all_values = [1, 1, 2]
all_values = []
for i in range(0, len(lists)):
all_values.append(lists[i].val)
while True:
min_value = min(all_values)
if min_value == 10**5: break # Finished merging of all linked lists
min_index = all_values.index(min_value)
if flag == 0: # To decide if it's the first node of our answer linked list to assign the "head"
head.next = lists[min_index]
dummy_front = lists[min_index]
flag = 1
else:
dummy_front.next = lists[min_index]
dummy_front = dummy_front.next
all_values.pop(min_index) # Pop the used smallest value
if not lists[min_index].next: # If the linked list has no other nodes, assign dummy_last to be its last node.
lists[min_index] = dummy_last
else:
lists[min_index] = lists[min_index].next
all_values.insert(min_index, lists[min_index].val) # Insert new value at min_index
return head.next
```

Leetcode provides an example:

```
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

My code's output is `ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: ListNode{val: 5, next: ListNode{val: 6, next: None}}}}}}}}`

, which is the right answer.
Please help! Thanks a lot!!!!

Comments:

2023-01-18 00:30:19

As always try the edge cases. If you work with lists, think about what happens when you get an empty one.

Answers(2) :

Realise that LeetCode runs 3 test cases, and so the error could be triggered in any of those three, not necessarily on the one where you have verified the output.

The error occurs when the following `if`

condition is true:

```
if not lists: return lists
```

In this case `lists`

is an empty list, but it still is a list, and you return it. That is not correct, as you should return a `ListNode`

or `None`

. In this case you should return `None`

.

Once this fix is applied, you'll bump into another problem in this part of the code:

```
for i in range(0, len(lists)):
all_values.append(lists[i].val)
```

`lists[i]`

might be `None`

(to denote an empty linked list) and in that case `lists[i].val`

is an invalid reference. To avoid this, you'd better start by removing all empty lists from `lists`

, right at the top of the function:

```
lists = list(filter(None, lists))
```

Once you've corrected that, you'll find out that your algorithm is too slow to pass the tests. The main source of the bad performance are these instructions:

```
min_value = min(all_values)
```

and:

```
min_index = all_values.index(min_value)
```

This will happen in each iteration, and as there could be up to 10000 lists, this is going to hit the performance.

To solve the performance problem, you could implement a divide-and-conquer algorithm: as long as you have `len(lists) > 2`

, split it into two halves and solve the problem for those two halves. You'll get two merged lists back, which you then have to merge. This way you only have to implement the logic for merging **two** lists and the divide-and-conquer logic.

Here is an implementation:

```
def mergeTwoLists(list1, list2):
result = prehead = ListNode()
while list1 and list2:
if list1.val < list2.val:
result.next = list1
list1 = list1.next
else:
result.next = list2
list2 = list2.next
result = result.next
result.next = list1 or list2
return prehead.next
def mergeLists(lists):
if len(lists) <= 2: # base case of recursion
return lists[0] if len(lists) == 1 else mergeTwoLists(*lists)
mid = len(lists) // 2
return mergeTwoLists(mergeLists(lists[:mid]), mergeLists(lists[mid:]))
class Solution:
def mergeKLists(self, lists):
if lists:
return mergeLists(lists)
```

You have made this far more complicated than is necessary.

Just build a list of all the values from all of the ListNodes. Then sort that list and then build a singly linked list.

```
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
vals = []
for node in lists:
while node:
vals.append(node.val)
node = node.next
if not vals:
return
vals.sort()
result = ListNode(vals[0])
prev = result
for v in vals[1:]:
prev.next = ListNode(v)
prev = prev.next
return result
```

Comments:

2023-01-18 00:30:19

Note that this has a worse asymptotic performance (the sort makes it O(n log n) at best) than a normal merge algorithm should have (which runs in O(n log k))

2023-01-18 00:30:19

@Voo I seem to have missed that part of the question where it refers to optimum performance. btw - I tried this in Leetcode and it beat 96% on performance

2023-01-18 00:30:19

Sure and it's definitely the most sensible answer for most scenarios. But given that LeetCode is used as a prep for job interviews - I'd expect a great candidate to also mention the difference in performance (and maybe have a discussion about why preferring a less efficient but much simpler algorithm initially is a good engineering decision).