题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

注意

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

方法一：

复杂度

时间复杂度：O(\max(m,n))，其中 mm 和 nn 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1)O(1) 的时间。

思路

1、注意该题目是链表，请不要直接使用列表去解答。

2、首先定义链表的头结点，然后定义当前节点 current_node 指向头结点，以及加法中的取整数 n，默认为 0。

3、当链表 l1 与链表 2 当前节点的值中存在有节点的值不为 None，或者 n 不为 0 时，计算三者之和。注意将节点的 None 值转为 0 计算。

4、将第三步中求和值除以 10 取整传给 n 用于下一个节点的计算。

5、将第三步中求和值除以 10 取余，然后创建一个新的节点。将该节点保存为current_node节点的next节点，完成链表的拼接。

6、然后将当前节点指向第五步中创建的新节点。

7、上一步处理完后将两个链表节点都指向自己本身的下一个节点，注意节点值为 None 时不存在 next 节点，选择不做处理

8、最后返回值应该为 result 节点的下一个节点的链表

代码

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result=ListNode(0)
        current_node = result
        n=0
        while l1 or l2 or n:
            num = (l1.val if l1 else 0)+(l2.val if l2 else 0)+n
            listnode = ListNode(num%10)
            n= num//10
            current_node.next=listnode
            current_node = current_node.next
            l1 = l1.next if l1 else None
            l2= l2.next if l2 else None
        return result.next

注意

该题目容易忽略的是直到所有链表及整数 n 都处理完，该程序才算处理完。

每次节点拼接到主链表时要注意下一步是将当前节点指向链表的最后一个节点。