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

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

``````class Solution(object):

"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

if l1 is None:
return l2

if l2 is None:
return l1

l1_len = self.list_length(l1)
l2_len = self.list_length(l2)

if carry == 1:
else:

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

``````

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