MARK一下，完全独立写出了这个回溯解法代表刷题进入不惧阶段

445. Add Two Numbers II

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        len1 = self.getLen(l1)
        len2 = self.getLen(l2)
        if len1 > len2:
            l2 = self.padLL(l2, len1-len2)
        elif len1 < len2:
            l1 = self.padLL(l1, len2-len1)
        carry, node = self.recurrAdd(l1, l2)
        if carry > 0:
            res = ListNode(carry)
            res.next = node
            return res
        return node
            
    def recurrAdd(self, l1, l2):
        if not l1:
            return 0, None
        c, r = self.recurrAdd(l1.next, l2.next)
        v = l1.val + l2.val + c
        res = ListNode(v%10)
        res.next = r
        return v//10, res
        
   
    def getLen(self, l):
        if not l:
            return 0
        res = 0
        while l:
            res += 1
            l = l.next
        return res
   
    def padLL(self, l, zeros):
        head = ListNode(0)
        node = head
        while zeros > 1:
            zeros -= 1
            node.next = ListNode(0)
            node = node.next
        node.next = l
        return head

77%还可以
飞机上刷题感觉有些开始刷透了，但是最近的面试居然一道算法题都没有，看来DS逐渐要和刷题流分道扬镳了。