Recursive processing O(n) time O(max(list1 length, list2 length)) space due to implicit stack


  • 0
        def addTwoNumbers(self, l1, l2):
    
            def get_length(head):
                l = 0
                while head:
                    l, head = l + 1, head.next
                return l
            
            def process(head):
                if not head: return 0
                nxt = process(head.next)
                head.val += nxt
                carry, head.val = head.val // 10, head.val % 10
                return carry
            
            lng1, lng2 = get_length(l1), get_length(l2)
            L1, L2 = l1, l2
            buffr = new = ListNode(None)
            while lng1 != lng2:
                if lng1 > lng2:
                    new.next = ListNode(L1.val)
                    L1, lng1, new = L1.next, lng1 - 1, new.next
                else:
                    new.next = ListNode(L2.val)
                    L2, lng2, new = L2.next, lng2 - 1, new.next
            while L1:
                new.next = ListNode(L1.val + L2.val)
                L1, L2, new = L1.next, L2.next, new.next
            if process(buffr.next):
                buffr.next, temp = ListNode(1), buffr.next
                buffr.next.next = temp
            return buffr.next
    

Log in to reply
 

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