# Python O(n) recursion solution without extraspace

• 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``````

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