解密链表大数相加的美妙算法｜LeetCode第2题"两数相加"
从生活到代码：解密链表大数相加的美妙算法从超市收银说起
想象你是一个超市收银员，正在计算两位顾客的购物总和。每位顾客的商品都按照从个位到高位的顺序摆放（比如54元就是先放4元商品，再放50元商品）。你需要一个一个地加起来，遇到超过10元的就进位。这个场景，恰恰就是我们今天要解决的链表两数相加问题的真实写照。
问题描述
LeetCode第2题"两数相加"要求：给你两个非空的链表，表示两个非负的整数。它们每个节点存储一个数字，并且是按照逆序方式存储的。请你将这两个数相加，并以相同形式返回一个表示和的链表。
例如：
输入：2 → 4 → 3, 5 → 6 → 4 解释：342 + 465 = 807 输出：7 → 0 → 8 输入：9 → 9 → 9, 1 解释：999 + 1 = 1000 输出：0 → 0 → 0 → 1 输入：0, 0 输出：0
思路分析：模拟手算加法
就像我们在纸上做加法一样：
[*]从最低位开始，两个数字相加
[*]如果和超过10，需要进位
[*]进位的1要加到下一位的计算中
这个过程完美映射到链表遍历上：从头节点（个位）开始，同时遍历两个链表，处理好进位关系。
代码实现与详解
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 创建哨兵节点，简化头节点的处理 ListNode dummy = new ListNode(0); ListNode current = dummy; // carry表示进位值，初始为0 int carry = 0; // 只要还有数字要相加，就继续循环 while (l1 != null || l2 != null || carry > 0) { // 获取当前位的值，如果链表已经遍历完则补0 int val1 = (l1 != null) ? l1.val : 0; int val2 = (l2 != null) ? l2.val : 0; // 计算当前位的和，包含前一位的进位 int sum = val1 + val2 + carry; // 计算新的进位值 carry = sum / 10; // 创建新节点，存储当前位的结果 current.next = new ListNode(sum % 10); current = current.next; // 移动到下一位 l1 = (l1 != null) ? l1.next : null; l2 = (l2 != null) ? l2.next : null; } return dummy.next; }
图解过程
例子：342 + 465 = 807 1) 初始状态： l1: 2 → 4 → 3 l2: 5 → 6 → 4 sum: dummy → 2) 处理个位：2 + 5 = 7 l1: 4 → 3 l2: 6 → 4 sum: dummy → 7 → 3) 处理十位：4 + 6 = 10 l1: 3 l2: 4 sum: dummy → 7 → 0 → (carry=1) 4) 处理百位：3 + 4 + 1(进位) = 8 sum: dummy → 7 → 0 → 8
特殊情况处理
这个解法优雅地处理了所有特殊情况：
[*]两个链表长度不同
[*]while条件包含了两个链表的检查
[*]短链表用0补齐
[*]最高位进位
[*]carry > 0 保证了最后的进位会被处理
[*]如：999 + 1 = 1000
[*]空链表
[*]初始的哨兵节点确保了结果链表始终有效
实现细节与优化
[*]时间复杂度：O(max(N, M))
[*]N和M是两个链表的长度
[*]只需要遍历一次最长的链表
[*]空间复杂度：O(max(N, M))
[*]需要存储结果链表
[*]结果的长度最多比最长的输入多1位（进位导致）
[*]代码优化技巧：
[*]使用哨兵节点简化头节点处理
[*]统一处理进位和数字相加
[*]优雅处理长度不同的情况
实际应用思考
这个算法的思想在很多场景中都有应用：
[*]大数计算
[*]处理超过语言内置数据类型范围的数字
[*]金融系统中的精确计算
[*]数据流处理
[*]流式处理大量数据
[*]实时计算系统
[*]进制转换
[*]模拟进位的思想可用于进制转换
[*]处理不同进制数的运算
扩展与提升
[*]如何处理负数？
[*]可以增加符号位
[*]需要考虑不同符号数字的相加
[*]如何处理正序存储的数字？
[*]可以先反转链表
[*]或者使用栈暂存节点
小结
链表两数相加的问题告诉我们：
[*]复杂问题可以通过模拟人工解决方式来简化
[*]良好的代码结构可以优雅处理各种边界情况
[*]数据结构的选择会影响问题的解决方案
温馨提示：在处理类似问题时，先想想人是如何解决的，再将这个过程转换为代码，往往能得到更清晰的思路。
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]