Leetcode-Medium-2 Add Two Number

题目

image.png
image.png

思路

给定两哥数字非负的单链表，每条单链表逆序存储着一个数字。将两条单链表存储的数字相加，并逆序放入单链表中。
解决办法：先初始化一个单链表节点。将给出的两个单链表串按位扫到两个空列表L1,L2中； 读取两个单链表，将其中存储的数字用整型表示成num1,num2，将读出的两个数字相加num1+num2=num3。计算结果后，逆序构造单链表L3,定义一个指针p指向首结点，通过移动p指针构造新链表，将num3做除法取余，取的余数就是num3当前的最末位数字，放入链表的头结点L3后面，再将新num3=num3/10再次取余数，这样到num3<10的时候，说明读取到了最初num3的最高位置，此时填入链表作为L3单链表的尾结点，链表构造结束。
时间复杂度：2O(n)+2O(n)+O(n) =O(n)

代码实现

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

class Solution:
    def addTwoNumbers(self,l1,l2):
        """
        :type l1,l2 :ListNode
        :rtype：ListNode
        """
        # 将两个单链表串按位扫到列表list1和list2中
        list1 = []
        list2 = []
        while l1 != None:
            list1.append(l1.val)
            l1 = l1.next
        while l2 != None:
            list2.append(l2.val)
            l2 = l2.next
        # 将两个数用整型num1,num2表示出来
        num1 = 0
        num2 = 0
        for i in range(len(list1)):
            num1 = list1[i] * (10 ** i) + num1
        for j in range(len(list2)):
            num2 = list2[j] * (10 ** j) + num2
        num = num1 + num2
        # 计算结果后，构造结果的单链表结果l3,逆序构造
        l3 = ListNode(0)
        p = l3
        # l3和p指向首节点，构造过程中l3不动,仍指向首节点，p进行构造移动
        while num >= 10:
            #temp = ListNode(None)
            p.val = num % 10
            p= p.next
            num = num/10
        p.val = num % 10
        return l3