Share my python solution, time O(n), constant space, recursive


  • 0
    S
    1. count length different
    2. count offset
    3. use l1 for the short one
    4. start recursive function, only if less or equal with 0, then move the short one
    5. create each node in the recursion
    6. add carry node if needed
    class Solution(object):
    
        def addTwoNumbers(self, l1, l2):
    
            len1 = 0
            cur = l1
            # count l1 length
            while cur:
                cur = cur.next
                len1 += 1
    
            len2 = 0
            cur = l2
            # count l2 length
            while cur:
                cur = cur.next
                len2 += 1
    
            # keep smallest in l1
            if len1 > len2:
                l1, l2 = l2, l1
                len1, len2 = len2, len1
    
            # count offset
            offset = len2 - len1
            head, carry = self.helper(l1, l2, offset)
            if carry:
                new = ListNode(carry)
                new.next = head
                head = new
            return head
    
        def helper(self, l1, l2, offset):
            if not l2:
                return None, 0
    
            v1, v2 = 0, l2.val
            head = None
            if offset <= 0:
                v1 = l1.val
                head, carry = self.helper(l1.next, l2.next, offset - 1)
            else:
                head, carry = self.helper(l1, l2.next, offset - 1)
            val = v1 + v2 + carry
            node = ListNode(val % 10)
            carry = val / 10
            if head:
                node.next = head
            return node, carry
    
    

Log in to reply
 

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