【每日算法】两数相加 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. 总结

• 高效性：通过逐位相加和进位处理，实现了链表的数字加法。
• 鲁棒性：处理了链表长度不一致和最后进位的情况。
• 通用性：适用于任意长度的数字相加。