Python Solution, O(n) time, without Modifying/Reversing Inputs. O(1) space?


  • 0
    R

    Do recursive function calls count towards time complexity? I used said function calls in place of explicitly using a stack.

    class Solution(object):
        
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            
            return self.add_two_numbers(l1, l2)
            
        def add_two_numbers(self, l1, l2):
            
            if l1 is None:
                return l2
            
            if l2 is None:
                return l1
            
            l1_len = self.list_length(l1)
            l2_len = self.list_length(l2)
            
            head = ListNode(None)
            
            carry, head.next = self.add_two_lists(l1, l1_len, l2, l2_len)
            
            if carry == 1:
                head.val = 1
                return head
            else:
                return head.next
    
            
        def add_two_lists(self, l1, l1_len, l2, l2_len):
            
            val1 = l1.val if l1_len >= l2_len else 0
            val2 = l2.val if l2_len >= l1_len else 0
            
            if l1_len > l2_len:
                carry, next_node = self.add_two_lists(l1.next, l1_len - 1, l2, l2_len)
            elif l1_len < l2_len:
                carry, next_node = self.add_two_lists(l1, l1_len, l2.next, l2_len - 1)
            elif l1.next is None and l2.next is None:
                carry = 0 
                next_node = None
            else:
                carry, next_node = self.add_two_lists(l1.next, l1_len - 1, l2.next, l2_len - 1)
                
            remainder = (val1 + val2 + carry) % 10    
            carry = (val1 + val2 + carry) / 10
            
            new_node = ListNode(remainder)
            new_node.next = next_node
            
            return (carry, new_node)
                
        @staticmethod        
        def list_length(l):
            count = 0
            while l is not None:
                l = l.next
                count += 1
            return count
            
        
    

Log in to reply
 

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