Merge K Sorted Lists (Leetcode 23)

DFS gives TLE. Strictly use Divide and Conquer for this problem

Problem Link: https://leetcode.com/problems/merge-k-sorted-lists/

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        
        def recursion(lists):
            
            n=len(lists)
            if(n==0):
                return None
            
            if(n==1):
                return lists[0]
            
            mid=n//2
            list1=recursion(lists[:mid])
            list2=recursion(lists[mid:])
            
            newlist=ListNode(-1)
            curr=newlist
            curr1=list1
            curr2=list2
            while(curr1 is not None and curr2 is not None):
                if(curr1.val <= curr2.val):
                    curr.next=curr1
                    curr1=curr1.next
                    curr=curr.next
                else:
                    curr.next=curr2
                    curr2=curr2.next
                    curr=curr.next
            if(curr1 is not None):
                curr.next=curr1
            if(curr2 is not None):
                curr.next=curr2
            return newlist.next
        
        return recursion(lists)