002-力扣刷题2-两数相加

题目描述:

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

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

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

示例：

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 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
        """
        def convert(list):  #3定义一个链表转换为数字的函数
            num = ''  #定义一个变量存储数字
            while list != None: #当链表指向不为空的时候取出这个数字并转换成字符串以便进行直接进行字符串相加
                num = str(list.val) + num
                list = list.next   #将list指向list的下一个
            return int(num)  #将字符串返回成数字

        num1, num2 = convert(l1), convert(l2)  #将两个链表转换成的数字相加
        num = num1 + num2
         #下面将转换好相加的数字转化成链表
        root = ListNode(num%10)
        l3 = root
        num = num // 10
        while num != 0:
            l3.next = ListNode(num%10)
            l3 = l3.next
            num = num // 10

        return root

上面的方式其实是一个取巧的操作 下面才是真正长链表操作的一个正确的解决方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 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 l1 == None:
            return l2
        if l2 == None:
            return l1
        carry = 0  #进位的大小
        dummy=ListNode(0) #创建一个新的链表  #dummy是根节点
        p=dummy #指针

        while l1 and l2:
            p.next =ListNode((l1.val+l2.val+carry)%10) #存储当前两个节点的值相加后进位剩下的数值
            carry=(l1.val+l2.val+carry)//10 #更新carry进位的大小
            l1=l1.next
            l2=l2.next
            p=p.next  #指针向下移动
        if l2:  #如果l2比较长的话
            while l2:
                p.next=ListNode((l2.val+carry)%10)
                carry=(l2.val+carry)//10
                l2=l2.next
                p=p.next
        if l1:  #如果l1比较长的话
            while l1:
                p.next=ListNode((l1.val+carry)%10)
                carry=(l1.val+carry)//10
                l1=l1.next
                p=p.next
        if carry == 1: #最终carry依旧有进位的话
            p.next=ListNode(1) #最高位溢出
        return dummy.next  #返回next的原因是跟节点是我们不需要的