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!!!!
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.
Divide and Conquer
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