Recursive Solution breaks Python


  • 0
    B

    Here is my code:

    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if not headA or not headB:
            return None
        elif headA.next is headB.next:
            return headA.next
        elif not headA.next or not headB.next:
            return None
        else:
            return self.getIntersectionNode(headA.next, headB.next)
    

    I believe that this is a valid solution, but I am hitting the stack depth limit (I think?) Please fix the test cases so that recursive solutions are valid.

    EDIT:
    This recursive solution is wrong, but the stack issue is apparently still a problem.


  • 0
    S

    Remember that Python imposes a limit on levels of recursion (1,000 by default, if I recall correctly). The longest lists have 10,000 nodes in the test cases, so of course your program would hit the recursion limit.

    I'm afraid the test cases do not need to be "fixed", but rather, you need to rethink about your implementation. The longest lists in the test cases are but less than a fraction of what you might actually encounter in real life. If your program cannot even handle those moderately big test cases, then we say it has a very poor scalability; and your interviewer will most certainly attack you a lot about this. Besides, the problem asks for constant space complexity, whereas your recursion solution uses at least O(n) space. For linked lists problems in general, it is usually a better idea to use iteration in order to achieve constant memory usage.


  • 0
    W

    Merge condition will never be satisfied, since you bail out when one of the list is null, the shorter one will bail out and cut short the recursion on the longer one. I think its difficult to solve this recursively, although you can solve it with 2 stacks.


  • 0
    W

    @stellari I dont think this is due to recursion, this code will never work


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.