Python O(n) recursion


  • 0
    R

    First, find the length of of two lists. Then sum this two list recursively.

    Anybody can do this without count length first, please tell me.

    Thanks,

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
    
            def depth(root1, root2, count1, count2):
                if not root1 and not root2:
                    return count1, count2
                elif root1 and root2:
                    return depth(root1.next, root2.next, 1 + count1, 1 + count2)
                elif root1:
                    return depth(root1.next, None, 1 + count1, count2)
                else:
                    return depth(None, root2.next, count1, 1 + count2)
    
            def helper(root1, root2, root_ans, max1, max2):
                if max1 > 1 or max2 > 1:
                    root_ans.next = ListNode(0)
                if max1 == 0 and max2 == 0:
                    return 0
                elif max1 == max2:
                    carry = helper(root1.next, root2.next, root_ans.next, max1 - 1, max2 - 1)
                elif max1 > max2:
                    carry = helper(root1.next, root2, root_ans.next, max1 - 1, max2)
                else:
                    carry = helper(root1, root2.next, root_ans.next, max1, max2 - 1)
    
                val1 = root1.val if max1 >= max2 else 0
                val2 = root2.val if max2 >= max1 else 0
                val_ans = val1 + val2 + carry
                carry = val_ans / 10
                val_ans %= 10
    
                if root_ans:
                    root_ans.val = val_ans
                return carry
    
            length1, length2 = depth(l1, l2, 0, 0)
    
            ans = ListNode(0)
            remainder = helper(l1, l2, ans, length1, length2)
    
            if remainder > 0:
                head = ListNode(remainder)
                head.next = ans
                ans = head
            return ans
    

Log in to reply
 

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