LeetCode2.两数相加

1. 题目大意

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

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

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

2. 思路分析

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

在上面的示例中，我想要计算342+465，为了符合人的计算直觉，同时为了解决进位的问题，用链表表示的是一个逆序的数字，比如342表示为链表就是243。知道上面的逻辑，按照正常的方法顺着走就好，难度相对不大。

值得注意的两个点：

1. 处理进位问题，我们可以单独设置一个变量来进行保存
2. 两数长度不一致的问题，我们对短的数字用0补齐
3. 如果最后两个数字相加>10，则需要额外增加一个节点表示进制。由于数的范围是1-9所以产生的进制最大只能是1

3. 代码示例

Java版本

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode res = new ListNode(0);// 保存进制记录int carry = 0;// 指向存储两数之和的位置ListNode cur = res; while(l1 != null || l2 != null){// 保持位数向平int x = l1 != null ? l1.val:0;int y = l2 != null ? l2.val:0;// 求和+进制int sum = x + y + carry;// 计算进数carry = sum / 10;sum %= 10;cur.next = new ListNode(sum);cur = cur.next;// 判断是否是最后一个元素if(l1 != null)l1 = l1.next;if(l2 != null)l2 = l2.next;if(carry == 1)cur.next = new ListNode(carry);}return res.next;}
}

Python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:res = ListNode(0)cur = res# 保存进制记录carry = 0while l1 is not None or l2 is not None or carry:# 短的一数字用0增加x = 0 if l1 is None else l1.valy = 0 if l2 is None else l2.val# 求和+进制sum = x+y+carrycarry = sum // 10sum = sum % 10cur.next = ListNode(sum)cur = cur.next# 判断是否是最后一个元素if l1 is not None:l1 = l1.nextif l2 is not None:l2 = l2.nextreturn res.next