2. Add Two Numbers

示例：

Input: (3 -> 4 -> 2) + (4 -> 6 -> 5)
Output: (8 -> 0 -> 7)
Explanation: 342 + 465 = 807.

这一题的坑在于要考虑进位，比如输入为5和5时，输出为0 -> 1。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return None
        root = res = ListNode(-1) # 先假设一个虚拟节点，最终返回这个虚拟节点的next即可
        carry = 0 # 先假设进位为0，便于后面的while判断
        while l1 or l2 or carry: # 把进位也加到判断条件中，就不用再额外对进位进行判断了
            val1 = val2 = 0
            if l1:
                val1 = l1.val
                l1 = l1.next
            if l2:
                val2 = l2.val
                l2 = l2.next
            carry, val = divmod(val1+val2+carry, 10) # carry=a//b, val=a%b
            res.next = ListNode(val)
            res = res.next
        return root.next

这道题有一个拓展，就是如果两个表示数字的链表不是从低位到高位，而是从高位到低位，要求输出也是从高位到低位，这时该如何处理呢？（参考：https://blog.csdn.net/u013378502/article/details/38467895）

比如：

Input: (3 -> 4 -> 2) + (4 -> 6 -> 5)
Output: (8 -> 0 -> 7)

解析：拓展题目看起来和原题差不多，但实际上会复杂更多。首先，因为两个链表的长度可能不一样，所以一开始要比较两个链表的长度，用0填充较短的链表。原题是求出新的节点后放在旧节点的后面，而拓展题目则需要添加节点到结果链表的前面，因此要用递归解决。递归需要传递两个参数：结果链表节点和进位。代码如下：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:
            return None
        
        # 查询两个链表的长度，并将短的链表用0填充
        len1 = self.getLength(l1)
        len2 = self.getLength(l2)
        l1 = self.paddingZero(l1, len2 - len1) if len1 < len2 else l1
        l2 = self.paddingZero(l2, len1 - len2) if len1 > len2 else l2

        # 对两个链表进行求和
        node, carry = self.addTwoList(l1, l2)

        # 判断最终结果是否有进位
        if carry:
            carry_node = ListNode(1)
            carry_node.next = node
            return carry_node
        else:
            return node
    
    def getLength(self, l): # 获取链表的长度
        length = 0
        while l:
            length += 1
            l = l.next
        return length
    
    def paddingZero(self, l, len_zero): # 用0填充短链表
        res = ListNode(-1)
        res.next = l
        for i in range(len_zero):
            node = ListNode(0)
            node.next = res.next
            res.next = node
        return res.next

    def addTwoList(self, l1, l2): # 递归求每一个节点的和
        if not l1 and not l2:
            res = None
            carry = 0
            return res, carry
        next_node, next_carry = self.addTwoList(l1.next, l2.next)
        cur_carry, cur_val = divmod(l1.val+l2.val+next_carry, 10)
        cur_node = ListNode(cur_val)
        cur_node.next = next_node
        return cur_node, cur_carry
        

if __name__ == '__main__':
    sol = Solution()
    node11 = ListNode(3)
    node12 = ListNode(4)
    node13 = ListNode(2)
    node21 = ListNode(4)
    node22 = ListNode(6)
    node23 = ListNode(5)
    node11.next = node12
    node12.next = node13
    node21.next = node22
    node22.next = node23
    y = sol.addTwoNumbers(node11, node21)
    while y:
        if y.next:
            print(y.val, end=' -> ')
        else:
            print(y.val)
        y = y.next
    # 输出结果：8 -> 0 -> 7