题解 | 两个链表生成相加链表 | 链表翻转相加

先分别翻转两个链表，将个位移到表头对齐，然后逐位相加（注意进位），相加之后生成的新链表也是个位在表头，最后需要再翻转一下。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1 , head2 ):
        def rev(root):
            """翻转链表"""
            pre = None
            curr = root
            while curr:
                # 存储前一个节点
                temp = pre
                # pre和curr后移，使pre的next指向temp
                pre = curr
                curr = curr.next
                pre.next = temp
            return pre
        
        def addTwoNumbers(l1,l2):
            """两数相加"""
            carry = 0
            ans = ListNode(0)
            head = ans
            while l1 or l2:
                """节点值存在num为val，否则为0"""
                num1 = l1.val if l1 else 0
                num2 = l2.val if l2 else 0
                sum = num1 + num2 + carry
                # tmp存储和的个位数,carry存储和的进位数
                tmp = sum % 10
                ans.next = ListNode(tmp)
                ans = ans.next
                carry = sum // 10
                l1 = l1.next if l1 else None
                l2 = l2.next if l2 else None
            # 最后可能还含有进位
            if carry:
                ans.next = ListNode(carry)
            return head.next
            
        l1 = rev(head1)
        l2 = rev(head2)
        res = addTwoNumbers(l1, l2)
        return rev(res)