Объединение отсортированных списков K – достигнута максимальная глубина рекурсии ⇐ Python

[Anonymous]

Я работал над Leetcode #23: Объединить отсортированные списки K (https://leetcode.com/problems/merge-k-s ... scription/) и столкнулся с проблемой.Я понимаю, что жизнеспособным решением является использование подхода «разделяй и властвуй», поэтому я попытался реализовать это с помощью рекурсии (например, как я представляю себе работу сортировки слиянием), но я продолжаю работать с максимальной глубиной рекурсии и не могу понять почему. Я также попробовал пройти через отладчик, и все работает нормально до последнего шага.
Вот мой код:

Код: Выделить всё

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 1:
return lists[0]
elif len(lists) == 2:
return self.merge2Lists(lists[0], lists[1])

v1 = self.mergeKLists(lists[:len(lists)//2])
v2 = self.mergeKLists(lists[len(lists)//2:])

return self.merge2Lists(v1, v2)

def merge2Lists(self, list1, list2):
result = ListNode()
cur = result

while list1 and list2:
if list1.val < list2.val:
cur.next = ListNode(list1.val)
list1 = list1.next
else:
cur.next = ListNode(list2.val)
list2 = list2.next
cur = cur.next

while list1:
cur.next = ListNode(list1.val)
list1 = list1.next
cur = cur.next

while list2:
cur.next = ListNode(list2.val)
list2 = list2.next
cur = cur.next

return result.next

Любая помощь в этом вопросе очень ценится, так как я боролся с этим уже несколько часов. (Кстати, я знаю, что для этого подхода «разделяй и властвуй» существуют итеративные решения, но я хотел попробовать заставить этот рекурсивный подход работать).

Подробнее здесь: https://stackoverflow.com/questions/792 ... th-reached