一.题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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 和 l2，并使用变量 carry 表示当前是否有进位。
每次遍历时，我们取出对应链表的当前位，计算它们与进位 carry 的和，然后更新进位的值，最后将当前位的值加入答案链表。如果两个链表都遍历完了，并且进位为 0 时，遍历结束。
最后我们返回答案链表的头节点即可。
时间复杂度 O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。忽略答案的空间消耗，空间复杂度 O(1)。
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 dummy = new ListNode(0);
// 初始化进位为0
int carry = 0;
// 当前节点指针，初始化为哑节点
ListNode cur = dummy;
// 当 l1、l2 或进位不为0时，继续循环
while (l1 != null || l2 != null || carry != 0) {
// 计算当前位的和，考虑 l1、l2 的当前值和进位
int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
// 更新进位
carry = s / 10;
// 创建新节点，存储当前位的结果
cur.next = new ListNode(s % 10);
// 移动当前节点指针
cur = cur.next;
// 移动 l1 和 l2 指针到下一个节点
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
// 返回结果链表的头节点
return dummy.next;
}
}
注释说明
哑节点：用于简化链表操作，最终返回结果链表的头节点。
进位：用于处理两个节点相加超过 10 的情况。
循环条件：当 l1、l2 或 carry 不为 0 时，继续处理。
计算和：考虑 l1、l2 的当前值和进位。
更新进位：通过 s / 10 计算新的进位。
创建新节点：存储当前位的结果。
移动指针：更新 cur、l1 和 l2 指针以处理下一个节点。Kotlin代码
/**
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* constructor(`val`: Int, next: ListNode?) : this(`val`) {
* this.next = next
* }
* }
*/
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
// 创建一个哑节点，作为结果链表的头节点
val dummy = ListNode(0)
// 初始化进位为0
var carry = 0
// 当前节点指针，初始化为哑节点
var cur = dummy
// 定义可变的 l1 和 l2
var p = l1
var q = l2
// 当 p、q 或进位不为0时，继续循环
while (p != null || q != null || carry != 0) {
// 计算当前位的和，考虑 p、q 的当前值和进位
val x = p?.`val` ?: 0
val y = q?.`val` ?: 0
val sum = x + y + carry
// 更新进位
carry = sum / 10
// 创建新节点，存储当前位的结果
cur.next = ListNode(sum % 10)
// 移动当前节点指针
cur = cur.next!!
// 移动 p 和 q 指针到下一个节点
p = p?.next
q = q?.next
}
// 返回结果链表的头节点
return dummy.next
}
}