算法2--两数相加

题目描述

解题思路

题目说的很详细了，也就是把每个数倒序写成链表进行输入，然后让你计算两个倒序数组的和，要保证跟预期的结果一样。

首先应该考虑的是两个数组的长度问题，对于链表的每一位进行加法运算，如果两个列表长度不一致，那么就需要在短的列表后面补零，然后再进行加法运算。

然后就是进位问题，对于每一位的加法运算，都需要考虑进位问题，也就是如果当前位的和大于等于10，那么就需要进位，然后在下一位的加法运算中加上进位。这是这题的难点。

最后就是链表这一数据结构本身的要求，链表只能通过指针遍历来访问每一个节点，所以需要注意指针的指向。

开始手搓！

题目已经给了链表的定义，所以我们可以直接使用这个数据结构。题目给出的的定义如下：

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

根据定义，我们可以通过.val获取指针所指向节点的值，通过.next获取指针所指向节点的下一个节点。

最后解题

我们可以定义一个新的链表，保存最后的运算结果；定义一个变量保存进位的值；然后通过判断链表是否结束，进行加法运算来确定新链表最新位的值和下一次的进位的值。

然后链表的指针和新链表的指针全部后移，继续循环。如果循环结束后进位不为0，那么就需要在新链表的末尾加上一个值为1的节点。

最后返回新链表的头节点。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        res = cur = ListNode()
        adder = 0

        while l1 or l2:
            num1 = l1.val if l1 else 0
            num2 = l2.val if l2 else 0
            cur.next = ListNode((num1+num2+adder)%10)
            adder = (num1+num2+adder)//10

            cur = cur.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next
        
        if adder: cur.next = ListNode(1)
        return res.next

尝试提交，通过，时间复杂度为O(Max(N,M))，其中N M为两个链表的长度。