背景
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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- 题目数据保证列表表示的数字不含前导零
感兴趣的小伙伴可以看leetcode原题：leetcode.cn/problems/ad…
分析
- 两个链表都不为空时，需要同时遍历两个链表，并计算每个节点相加的结果；
- 如果相加结果超过10，需要对结果求余，余数才是当前节点的val，多出的放到后面节点；
- 如果相加结果不超过10，那么直接就是当前节点的val；
- 如果链表1不为空，只遍历链表1，同时计算链表1节点的val和前面进位的值相加，因为前面相加的结果可能进位；
- 也是需要判断是否超过10，超过10进位，不超过10就直接创建新的节点；
- 如果链表2不为空，遍历链表2，同样计算链表2节点的val和进位值的和；
- 如果大于10，继续进位，否则创建新的节点；
- 最后一步判断进位值是否大于0，如果大于0还需要再创建一个新的节点；否则结束；
java实现
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 创建一个临时链表 ListNode tmp = new ListNode(0); // 再创建一个引用指向临时节点，代码执行过程中，该引用不动，只改变临时链表 ListNode result = tmp ; // 进位值，默认是0 int nextVal = 0; // 如果链表1和链表2不为空 while(l1!=null && l2!=null){ // 取出l1节点的值 int val1 = l1.val; // 取出l2节点的值 int val2 = l2.val; // 把l1节点的值+l2节点的值+进位的值 int sum = val1+val2+nextVal; // 需要对10求余才能得到新节点的值 int newVal = sum%10; // 计算下一个进位值 nextVal = sum/10; // 创建新的节点 tmp.next = new ListNode(newVal); // 移动临时链表，为下一个节点做准备 tmp = tmp.next; // 移动l1链表 l1 = l1.next; // 移动l2链表 l2 = l2.next; } // 如果链表1不为空 while(l1!=null){ // 取出l1节点的值 int val1 = l1.val; // 计算和进位值的和 int sum = val1+nextVal; // 计算新节点的值，需要求余 int newVal = sum%10; // 计算下一个进位制 nextVal = sum/10; // 创建新的节点 tmp.next = new ListNode(newVal); // 移动临时链表 tmp = tmp.next; // 移动l1链表 l1 = l1.next; } // 如果链表2不为空 while(l2!=null){ // 取出l2节点的值 int val2 = l2.val; // 计算l2节点和进位值的和 int sum = val2+nextVal; // 计算新节点的值 int newVal = sum%10; // 计算下一个进位制 nextVal = sum/10; // 创建新的节点 tmp.next = new ListNode(newVal); // 移动临时链表 tmp = tmp.next; // 移动l2链表 l2 = l2.next; } // 判断进位值是否大于0 if(nextVal>0){ // 如果进位值大于0，那么还需要再创建一个新节点 tmp.next = new ListNode(nextVal); } // 返回最终结果，因为result一直指向临时链表的第一个节点 return result.next; } 复制代码
【注意】：因为这是单向链表，为了能够在最后返回结果时拿到链表的头节点，我们需要额外创建一个引用指向临时链表的头节点，这样的话，临时链表计算完毕后，我们就可以直接返回头节点了。
python实现
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: # 创建临时链表 tmp = ListNode() # 指向头节点，以便后续返回结果 result = tmp # 默认进位值为0 next_val = 0 # 如果l1和l2都不为空 while l1 is not None and l2 is not None: # 取出l1节点的值 val1 = l1.val # 取出l2节点的值 val2 = l2.val # 计算l1节点的值+l2节点的值+进位值 sum = val1 + val2 + next_val # 计算新节点的值 new_val = sum % 10 # 计算下一个进位值 next_val = sum // 10 # 创建新节点 tmp.next = ListNode(new_val) # 移动临时链表 tmp = tmp.next # 移动l1链表 l1 = l1.next # 移动l2链表 l2 = l2.next # 如果l1链表不为空 while l1 is not None: # 取出l1节点的值 val1 = l1.val # 计算l1节点的值+进位值 sum = val1 + next_val # 计算新节点的值 new_val = sum % 10 # 计算下一个进位值 next_val = sum // 10 # 创建新节点 tmp.next = ListNode(new_val) # 移动临时链表 tmp = tmp.next # 移动l1链表 l1 = l1.next # 如果l2链表不为空 while l2 is not None: # 取出l2节点的值 val2 = l2.val # 计算l2节点的值+进位值 sum = val2 + next_val # 计算新节点的值 new_val = sum % 10 # 计算下一个进位值 next_val = sum // 10 # 创建新节点 tmp.next = ListNode(new_val) # 移动临时链表 tmp = tmp.next # 移动l2链表 l2 = l2.next # 如果进位值大于0 if next_val>0: # 如果进位值大于0，我们还需要再多创建一个新节点 tmp.next = ListNode(next_val) # 返回临时链表的第二个节点 return result.next 复制代码
【注意】在python中，整除需要使用//才行，否则会计算出小数点。
rust实现
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // 因为需要移动l1链表，所以我们需要额外创建引用 let mut tmp_l1 = &l1; // 因为需要移动l2链表，所以我们需要额外创建引用 let mut tmp_l2 = &l2; // 我们创建一个头节点 let mut result = Some(Box::from(ListNode::new(0))); // 创建一个临时引用 let mut tmp = result.as_mut(); // 进位值，默认是0 let mut next_val = 0; // 如果l1和l2都有值 while let (Some(node1), Some(node2)) = (tmp_l1, tmp_l2) { // 计算l1节点+l2节点+进位值 let sum = node1.val + node2.val + next_val; // 计算新节点的值 let new_val = sum % 10; // 计算下一个进位值 next_val = sum / 10; // 取出临时节点 let tmp_node = tmp.unwrap(); // 设置新节点 tmp_node.next = Some(Box::from(ListNode::new(new_val))); // 移动临时链表 tmp = tmp_node.next.as_mut(); // 移动l1链表 tmp_l1 = &node1.as_ref().next; // 移动l2链表 tmp_l2 = &node2.as_ref().next; } // 如果l1不为空 while let (Some(node1), None) = (tmp_l1, tmp_l2) { // 计算l1节点+进位值 let sum = node1.val + next_val; // 计算新节点的值 let new_val = sum % 10; // 计算下一个进位值 next_val = sum / 10; // 取出临时节点 let tmp_node = tmp.unwrap(); // 创建新节点 tmp_node.next = Some(Box::from(ListNode::new(new_val))); // 移动临时链表 tmp = tmp_node.next.as_mut(); // 移动l1链表 tmp_l1 = &node1.as_ref().next; } // 如果l2链表不为空 while let (None, Some(node2)) = (tmp_l1, tmp_l2) { // 计算l2节点+进位值 let sum = node2.val + next_val; // 计算新节点的值 let new_val = sum % 10; // 计算下一个进位值 next_val = sum / 10; // 取出临时节点 let tmp_node = tmp.unwrap(); // 创建新节点 tmp_node.next = Some(Box::from(ListNode::new(new_val))); // 移动临时链表 tmp = tmp_node.next.as_mut(); // 移动l2链表 tmp_l2 = &node2.as_ref().next; } // 如果进位值不为空 if next_val > 0 { // 取出临时节点 let tmp_node = tmp.unwrap(); // 再创建一个新节点 tmp_node.next = Some(Box::from(ListNode::new(next_val))); } // 返回结果 result.unwrap().next } 复制代码
【注意】在rust中一定要注意引用和解引用的使用，还有就是可变与不可变的使用。
以上就是我们使用三种编程语言针对【两数相加】这个算法题的题解，觉得不错的小伙伴也可以用自己喜欢的语言给出相应的题解。
作者：梦想实现家_Z
链接：https://juejin.cn/post/7134231722043899917
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
