每日算法两数相加-LeetCode
目录
【每日算法】两数相加 LeetCode
这段代码实现了一个名为 AddTwoNumbers 的方法，用于将两个用链表表示的非负整数相加，并返回一个新的链表表示它们的和。
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
ListNode head = new ListNode(0);
ListNode cur = head;
int carry = 0;
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;
// 当前节点 取余数
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null)
{
l1 = l1.next;
}
if (l2 != null)
{
l2 = l2.next;
}
}
if (carry > 0)
{
cur.next = new ListNode(carry);
}
return head.next;
}以下是逐步解析：
1. 方法功能
- 输入：两个链表
l1和l2，每个节点表示一个数字的一位（逆序存储，即个位在链表头部）。 - 输出：一个新的链表，表示
l1和l2相加的结果（同样逆序存储）。
2. 代码逐行解析
(1) 初始化虚拟头节点
ListNode head = new ListNode(0);
ListNode cur = head;- 作用：创建一个虚拟头节点
head，用于简化链表操作。 cur是一个指针，用于遍历和构建结果链表。
(2) 初始化进位
int carry = 0;- 作用：记录当前位的进位值（初始为
0）。
(3) 遍历链表
while (l1 != null || l2 != null)- 条件：只要
l1或l2中还有未处理的节点，就继续循环。
(4) 计算当前位的值
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
int sum = x + y + carry;- 逻辑：
- 如果
l1或l2已经遍历完，则用0代替。 sum是当前位的和（包括进位）。
- 如果
(5) 处理进位
carry = sum / 10;- 逻辑：计算新的进位值（
sum / 10的整数部分）。
(6) 创建新节点
cur.next = new ListNode(sum % 10);
cur = cur.next;- 逻辑：
sum % 10是当前位的值（去掉进位后的个位数）。- 将新节点添加到结果链表中，并移动
cur指针。
(7) 移动输入链表的指针
if (l1 != null)
{
l1 = l1.next;
}
if (l2 != null)
{
l2 = l2.next;
}- 逻辑：如果
l1或l2未遍历完，则移动到下一个节点。
(8) 处理最后的进位
if (carry > 0)
{
cur.next = new ListNode(carry);
}- 逻辑：如果遍历结束后仍有进位（
carry > 0），则在结果链表的末尾添加一个新节点。
(9) 返回结果
return head.next;- 作用：跳过虚拟头节点，返回真正的结果链表。
3. 关键点分析
(1) 逆序存储的优势
- 链表的头部是个位，方便从低位到高位逐位相加。
- 进位可以自然地向高位传递。
(2) 虚拟头节点的作用
- 简化链表操作，避免单独处理头节点的情况。
(3) 时间复杂度
- O(max(m, n))：其中
m和n分别是l1和l2的长度。 - 需要遍历较长的链表。
(4) 空间复杂度
- O(max(m, n))：结果链表的长度最多为
max(m, n) + 1（如果有进位）。
4. 示例验证
示例 1
l1 = 2 -> 4 -> 3（表示数字 342）
l2 = 5 -> 6 -> 4（表示数字 465）
// 输出：7 -> 0 -> 8（表示 342 + 465 = 807）示例 2
l1 = 9 -> 9 -> 9（表示数字 999）
l2 = 1（表示数字 1）
// 输出：0 -> 0 -> 0 -> 1（表示 999 + 1 = 1000）示例 3
l1 = null（表示数字 0）
l2 = 1 -> 2（表示数字 21）
// 输出：1 -> 2（表示 0 + 21 = 21）5. 总结
- 高效性：通过逐位相加和进位处理，实现了链表的数字加法。
- 鲁棒性：处理了链表长度不一致和最后进位的情况。
- 通用性：适用于任意长度的数字相加。