给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#方法一：将链表转换成数，相加后再转换成链表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        #得到数
        def getnum(l1:ListNode)->int:
            t=1
            s=0
            node=l1
            while(node!=None):
                s+=t*node.val
                t=t*10
                node=node.next
            return s
        num1=getnum(l1)
        num2=getnum(l2)
        sum=num1+num2
        #再生成链表
        tnone=ListNode()
        t=tnone
        while(sum//10!=0):
            v=sum%10
            t.next=ListNode(v)
            sum=sum//10
            t=t.next
        #加最后一项
        t.next=ListNode(sum)
        return tnone.next

#方法2
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 链表每项相加，进位
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        #链表长度
        def length_of_listnode(l1:ListNode)->int:
            t=1
            l=l1
            while(l!=None):
                t+=1
                l=l.next
            return t
        length1=length_of_listnode(l1)
        length2=length_of_listnode(l2)
        #保证l1较长
        if(length1<length2):
            l1,l2=l2,l1
        #进位
        jw=0
        #指向l1，l2的指针
        p1=l1
        p2=l2
        #创建一个空链表
        p=ListNode()
        pa=p#保存新链表的首项
        #每个数相加，进位
        while(p2!=None):
            p.next=ListNode((p1.val+p2.val+jw)%10)
            jw=(p1.val+p2.val+jw)//10
            p=p.next
            p1=p1.next
            p2=p2.next
        #如果有进位，p1 不空继续添加新节点
        while(jw and p1!=None):
            p.next=ListNode((p1.val+jw)%10)
            jw= (p1.val+jw)//10
            p=p.next
            p1=p1.next
        if(not jw):
             p.next=p1
        if(jw and p1==None):
            p.next=ListNode(jw)
        return pa.next