# Python O(n) recursion

• First, find the length of of two lists. Then sum this two list recursively.

Anybody can do this without count length first, please tell me.

Thanks,

``````class Solution(object):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""

def depth(root1, root2, count1, count2):
if not root1 and not root2:
return count1, count2
elif root1 and root2:
return depth(root1.next, root2.next, 1 + count1, 1 + count2)
elif root1:
return depth(root1.next, None, 1 + count1, count2)
else:
return depth(None, root2.next, count1, 1 + count2)

def helper(root1, root2, root_ans, max1, max2):
if max1 > 1 or max2 > 1:
root_ans.next = ListNode(0)
if max1 == 0 and max2 == 0:
return 0
elif max1 == max2:
carry = helper(root1.next, root2.next, root_ans.next, max1 - 1, max2 - 1)
elif max1 > max2:
carry = helper(root1.next, root2, root_ans.next, max1 - 1, max2)
else:
carry = helper(root1, root2.next, root_ans.next, max1, max2 - 1)

val1 = root1.val if max1 >= max2 else 0
val2 = root2.val if max2 >= max1 else 0
val_ans = val1 + val2 + carry
carry = val_ans / 10
val_ans %= 10

if root_ans:
root_ans.val = val_ans
return carry

length1, length2 = depth(l1, l2, 0, 0)

ans = ListNode(0)
remainder = helper(l1, l2, ans, length1, length2)

if remainder > 0: