[Python] Merge K Sorted Lists - Maximum Recursive Depth Reached

I've been working on Leetcode #23: Merge K Sorted Lists (https://leetcode.com/problems/merge-k-sorted-lists/description/) and come across a problem.

I understand that a viable solution is using a divide and conquer approach, so I tried to implement this using recursion (like how I imagine Merge Sort works), but I keep running into the maximum recursion depth and can't figure out why. I tried stepping through the debugger as well and it all seems to work fine until the last step.

Here is my code:

# 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


Any help on this is much appreciated, as I have been struggling with this for hours. (BTW, I know there are iterative solutions for this divide and conquer approach, but I wanted to try and get this recursive one to work).

Continue reading...