@Python

Python LeetCode2_两数之和

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

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

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

示例：

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

**题目分析：**这是一道数据结构链表的题目，主要问题在于链表节点整数相加后会产生进位问题。
**解决方案1：**将链表print为数组，数组元素对应位置相加（利用十进制位数转换），输出一个整数，这样不用考虑两个数组长度不相等的问题，再利用取余逆序输出。

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

class Solution:
    
    def get_list(l: ListNode):
        getlist = []
        length = 0
        p = l
        while p is not None:
            getlist.append(p.val)
            length += 1
            p = p.next
        return getlist, length
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        getlist1, length1 = Solution.get_list(l1)
        getlist2, length2 = Solution.get_list(l2)
        if (length1 >length2):
            length2 = length1
            length=getlist2.extend([0] * (length1 - length2))
        else:
            length=length1 = length2
            getlist1.extend([0] * (length2 - length1))
        sum1=0
        sum2=0
        for i in range(len(getlist1)):
            sum1+=getlist1[i]*(10**i)
        for i in range(len(getlist2)):
            sum2+=getlist2[i]*(10**i)
        twosum=sum1+sum2
        addsum=[]
        tag=1
        while(tag!=0):
            addsum.append(twosum%10)
            tag=twosum//10
        return addsum

出现的问题：复杂度过大,没有考虑到链表的特性，盲目转化为数组运算，得不偿失。
新的语法get：两个数组按元素四则运算：sum=list（map(lambda x:x[0]+x[1]),zip(实参1，实参2)）

**解决方案2：**针对链表每个节点数据域相加得到的进位情况进行取余和取整（进位为1），同时输出链表的下一个指向为1。用tag标记进位，并加入每次取余和取整运算之中。类似加法器。链表长度不相等用是否为None判断。

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry=0                          #进位
        #初始化空链表头节点
        temp = ListNode(0)
        res=temp
        # 如果有一个链表为空，返回另外一个
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        while(l1 or l2):                #两个链表均不空继续执行 
            list_sum=0
            if l1:                       #不能用循环，而是判断
                list_sum+=l1.val
                l1=l1.next
            if l2:
                list_sum+=l2.val
                l2=l2.next
            rem=(list_sum+carry)%10          #取余，生成新链表节点存储值
            carry=(list_sum+carry)//10        #进位
            #res.next=rem 错误
            res.next=ListNode(rem)            #更新新链表元素
            res=res.next                              #更新节点
            if carry:
                res.next=ListNode(1)      #新链表进位
        res=temp.next                         #因为self.next = None，尾节点
        del temp
        return res