Is an AC recursive solution possible with python?


  • 0
    R

    I tried to solve the problem recursively using Python. But I got a run time error when there are 5000 nodes in the list. I assume that it is an issue with the recursion stack. Please correct me if I am wrong.

    The same solution, when written in Java, gave 291 ms, which is good for a Java solution on leetcode. I wonder wheter a AC recursive solution is possible with python. If it is possible, please let me know what is wrong with my program.

    def reverseList(self, head):
            def reverseHelper(previous,current):
                if current.next:
                    last = reverseHelper(current,current.next)
                    current.next = previous
                    return last
                else:
                    current.next = previous
                    return current
                
            if head:
                return reverseHelper(None,head)
            else:
                return None

  • 0
    A

    you can pass the case locally by modifing the recursion limit value in your code,
    import sys sys.setrecursionlimit(10000)

    But, to pass the OJ, have no idea.


  • 1
    I

    sure

    class Solution:
        def recursively(self, headOld, headNew) :
            temp = headOld
            headOld = headOld.next
            temp.next = headNew
            
            if headOld :
                return self.recursively(headOld, temp)
            else :
                return temp
    
        # @param {ListNode} head
        # @return {ListNode}
        def reverseList(self, head) :
            if head is None :
                return None
                
            return self.recursively(head, None)

  • 0

    Thanks for your feedback. I have raised the memory limit for Python and your solution should AC now.


  • 0
    F

    The following code will occur "stack overflow" problem.What is the difference between your code and the following code? Thanks!

    def reverseLstR(self, nxt, pre):
        if not nxt:
            return pre
        next = nxt.next
        nxt.next = pre
        return self.reverseLstR(next, nxt)
        
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        return self.reverseLstR(head, None)
    

  • 0
    I

    I have tried your codes......and it's accepted.


Log in to reply
 

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