给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
示例
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
在做这道题之前，我们需要简单地了解一下什么是链表。在链表中，每个数据项都被包含在“链结点（Link）”。一个链结点是每个类的对象，这个类可以叫做Link。每个Link对象中都包含一个对下一个链结点引用的字段（通常叫做next）。但是，链表本身的对象中有一个字段指向第一个链结点的引用。以下是链表与结点之间的关系。
这里使用Java为例，创建一个Link类，它包含了一些数据（实际项目也是比这多的）和下一个链结点的引用：
class Link{
//数据的定义
public int iData;
public double dDate;
//相关下一个链表
public Link next;
}
解决方案
思路
有了以上的基础了，我们可使用结点数据变量进行跟踪进位，并从包含最低有效位的表头开始模拟逐相加的过程。
在这里插入图片描述
以上是对两数相加方法的可视化：342+465=807,每个结点都包含一个数字，并且是使用逆序存储的。
算法
就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表 l1 和 l2的表头开始相加。由于每位数字都应当处于0…9 的范围内，我们计算两个数字的和时可能会出现“溢出”。例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为 2，并将进位 carry = 1带入下一次迭代。进位 carry必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。
伪代码如下：
- 将当前结点初始化为返回列表的哑结点。
- 将进位 carrycarry 初始化为 00。
- 将 pp 和 qq 分别初始化为列表 l1l1 和 l2l2 的头部。
- 遍历列表l1和l2直至它们的尾端。
- 将 x设为结点 p 的值。如果 p 已经到达 l1 的末尾，则将其值设置为 0。
- 将 y设为结点 q 的值。如果 q 已经到达 l2 的末尾，则将其值设置为 0。
- 设定 sum = x + y + carry。
- 更新进位的值，carry = sum / 10。
- 创建一个数值为 (sum mod 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
- 同时，将 p 和 q 前进到下一个结点。
- 检查 carry = 1是否成立，如果成立，则向返回列表追加一个含有数字 1 的新结点。
- 返回哑结点的下一个结点。
请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。
请特别注意以下情况：
在写代码之前知道数据类型中基本类型以及引用类型之间的区别，本题也需要注意引用类型的使用。
Java代码
//创建一个链表的类
class ListNode {
//结点的值
int val;
//指向下一个结点
ListNode next;
//通过参数添加值
ListNode(int x){
val=x;
}
}
public class Demotest {
public static void main(String[] args) {
//定义两个结点,并添加信息
ListNode l1=new ListNode(2);
l1.next=new ListNode(4);
l1.next.next=new ListNode(3);
ListNode l2=new ListNode(5);
l2.next=new ListNode(6);
l2.next.next=new ListNode(4);
ListNode result_listnode = new Demotest().addTwoNumbers(l1,l2);
//打印计算的结果
while(result_listnode!=null) {
System.out.println(result_listnode.val);
result_listnode=result_listnode.next;
}
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//创建一个计算结果的链表
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
//定义一个用于进位的值
int carry = 0;
//通过循环开始计算
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
//链表更新
if (p != null) p = p.next;
if (q != null) q = q.next;
}
//验证循环结束后是否还有进位值
if (carry > 0) {
curr.next = new ListNode(carry);
}
//返回去掉创建含有0的链表
return dummyHead.next;
}
}
需要说明的是：原题只要我们写出计算的函数，不需要写出计算的主函数，这里为了自己学习，写出全部程序。
程序运行结果：
Python代码
#Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
#创建一个对象
class Solution:
def addTwoNumbers(self,l1,l2):
#定义一个ListNode
dummyHead=ListNode(0)
p=l1
q=l2
curr=dummyHead
carry=0
while p!=None or q!=None:
x=p.val if p!=None else 0
y=q.val if q!=None else 0
Sum=carry+x+y
carry=int(Sum/10)
curr.next = ListNode(Sum%10)
curr=curr.next
if p!=None:p=p.next
if q!=None:q=q.next
if carry>0:curr.next=ListNode(carry)
return dummyHead.next
#创建l1
l1=ListNode(2)
temp=l1
l1.next=ListNode(4)
l1.next.next=ListNode(3)
#创建l2
l2=ListNode(5)
l2.next=ListNode(6)
l2.next.next=ListNode(4)
#开始运算
result=Solution().addTwoNumbers(l1, l2)
#打印测试
while result!=None:
print(result.val)
result=result.next
复杂度分析
- 时间复杂度：O(max(m,n)，假设 m 和 n分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m,n) 次。
- 空间复杂度：O(max(m,n))， 新列表的长度最多为 max(m,n)+1。