本文正在参加「Java主题月 - Java 刷题打卡」，详情查看 活动链接

一、题目描述

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

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

你可以假设除了数字 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
• 题目数据保证列表表示的数字不含前导零

二、思路分析

题目解读

这是一道两数相加的题目，并把两数分别存放到两个不同的链表中，链表中的每一节点存放一位数，并以逆序存放，如：链表 l1 : [2,4,3] ，则代表数字 342 ；链表 l2 : [5,6,4] ,则代表数字 465 。此时，两数相加得到的输出链表为 [7,0,8] ( 342 + 465 = 807 )。另：两数相加必须要满足运算规则。

知识点复习

本题中提及到了 链表 ，在此对 链表 进行复习回顾，更有助于对此题的解答。

和数组相同，链表是一种线性表结构。从底层存储结构上看，链表不需要一整块连续的存储空间，而是通过“指针”将一组零散的内存块串联起来使用。链表中的每个内存块被称为链表的“结点”，每个结点除了要存储数据外，还需要记录上(下)一个结点的地址。

特点：

• 插入、删除数据效率高，只需要考虑相邻结点的指针改变，不需要搬移数据，时间复杂度是 O(1) 。
• 随机查找效率低，需要根据指针一个结点一个结点的遍历查找，时间复杂度为 O(n) 。
• 与内存相比，链表的空间消耗大，因为每个结点除了要存储数据本身，还要储存上(下)结点的地址。

常用的链表类型:

• 单链表

• 循环链表

• 双向链表

• 双向循环列表

本题目中用到的是最为简单“单链表”。

算法分析

本题难度：★★★☆☆

本题的关键在于对题目的充分理解，正确读懂题目就离成功不远了。我们只需遍历两个数的链表 l1 、 l2 ，逐位计算它们之和 n1 + n2 ，并需要考虑计算结果是否进位(即： n1 + n2 >10 的结果)。