LeetCode 2. 两数相加 --- 链表、模拟

题目简述：给定两个非空的链表，表示两个非负整数，它们每位数字都是按照逆序方式存储的。要求将这两个数相加，并以相同形式返回一个表示和的链表。每个链表中的节点只能存储一位数字，并且除了数字 0 之外，这两个数都不会以 0 开头。

1. 思路与算法

使用迭代的方法来实现链表的相加。从两个链表的头节点开始，依次将对应位置的数字相加，并保留进位。在遍历完两个链表的所有节点之后，如果还存在进位，就需要在结果链表中追加一个节点来存储进位。

2. 代码

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) {// 获取当前节点的值，如果链表已经遍历完成，则默认为 0int x = (p != null) ? p.val : 0;int y = (q != null) ? q.val : 0;// 计算当前节点的和，包括进位int sum = x + y + carry;// 更新进位carry = sum / 10;// 创建新节点，存储当前节点的值curr.next = new ListNode(sum % 10);// 将指针 curr 向后移动一位curr = curr.next;// 移动指针 p 和 q，准备下一轮循环if (p != null) p = p.next;if (q != null) q = q.next;}// 处理最后的进位，如果有进位则在结果链表的末尾添加一个节点if (carry > 0)curr.next = new ListNode(carry);// 返回结果链表的头节点return dummyHead.next;}

3. 复杂度分析

• 时间复杂度：遍历两个链表一次，时间复杂度为 O(max(m, n))，其中 m 和 n 分别是两个链表的长度。
• 空间复杂度：除了存储结果的链表以外，只需要常数级别的额外空间，因此空间复杂度为 O(1)。