Merge K Sorted Lists - Maximum Recursive Depth Reached

I've been working on Leetcode problem #23: Merge K Sorted Lists:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

I encountered the following 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 error 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

The following three test cases are run when clicking Run in the LeetCode interface. They are encoded in this JSON format:

1. [[1,4,5],[1,3,4],[2,6]]
2. []
3. [[]]

I get this error message:

Runtime Error
RecursionError: maximum recursion depth exceeded
  [Previous line repeated 997 more times]
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    v1 = self.mergeKLists(lists[:len(lists)//2])
Line 6 in mergeKLists (Solution.py)
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

I know there are iterative solutions for this divide and conquer approach, but I wanted to try and get this recursive one to work.

Where is the mistake?

The problem is just with one specific case, where the input lists is empty. You have not dealt with that base case, so that you fall into an infinite recursion.

Just add that base case and you're fine:

        if not lists:
            return None

Unrelated remarks

The above fixes the problem. But maybe some other things you could consider:

You don't need to deal with the last base case in your code, as it will be dealt with properly in the recursive case; you can remove this:

        elif len(lists) == 2:
            return self.merge2Lists(lists[0], lists[1])

It is nice that you made a new linked list without mutating the original linked lists. This is good practice. Do note however, that it comes at the cost of a O(𝑛) space complexity (here 𝑛 is the total number of nodes). As an alternative, you could try to re-use the existing nodes and just wire them together into the result list, which admittedly mutates the original lists, but for this challenge that seems to be fine.