Python O(n) recursion solution without extraspace


  • 0
    Y

    class Solution(object):
    def getLength(self, l1):
    result = 0
    while l1:
    l1 = l1.next
    result += 1
    return result
    def dfs(self, long, short, shift):
    if shift > 0:
    carry, next = self.dfs(long.next, short, shift-1)
    val = (long.val + carry)%10
    carry = (long.val + carry)/10
    node = ListNode(val)
    node.next = next
    return carry, node
    else:
    if long.next == None:
    val = (long.val + short.val)%10
    carry = (long.val + short.val)/10
    return carry, ListNode(val)
    else:
    carry, next = self.dfs(long.next, short.next, shift)
    val = (long.val + short.val + carry)%10
    carry = (long.val + short.val + carry)/10
    node = ListNode(val)
    node.next = next
    return carry, node
    def addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """

        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val == 0:
            return l2
        if l2.val == 0:
            return l1
        len1 = self.getLength(l1)
        len2 = self.getLength(l2)
        if len1 > len2:
            long = l1
            short = l2
        else:
            long = l2
            short = l1
        
        root = ListNode(0)
        carry, next = self.dfs(long, short, abs(len1-len2))
        if carry == 1:
            root.val = 1
            root.next = next
            return root
        else:
            return next

Log in to reply
 

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