Hot 100 --- 两数相加

本文概览本文以LeetCode经典题目两数相加为例从题目特点入手重点讲解链表倒序存储带来的便利以及如何通过sum和carry两个变量优雅处理进位问题一、题目二、题目分析给定两个非空链表分别表示两个非负整数。它们的每位数字都是按照逆序存储的每个节点只能存储一位数字目标将两个数相加并以相同形式返回一个表示和的链表核心特点倒序存储题目中链表是倒序存储的比如数字342表示为2 → 4 → 3这其实非常方便因为加法本来就是从最低位开始算的。倒序链表的头节点刚好就是最低位所以我们不需要反转链表直接从头开始逐位相加即可核心难点进位处理这道题思路不难真正容易写乱的是进位当前两位相加如果大于等于 10就需要给下一位进 1。链表是动态创建的不能提前给temp.next.next加 1所以需要用变量来保存进位思路概览Java实现代码如下public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode temp new ListNode(-1); ListNode head temp; // 初始化 int carry 0; while (l1 ! null || l2 ! null || carry ! 0) { int sum carry; if (l1 ! null) { sum l1.val; l1 l1.next; } if (l2 ! null) { sum l2.val; l2 l2.next; } // 处理进位 carry sum / 10; sum % 10; // 创建新节点 temp.next new ListNode(sum); temp temp.next; } return head.next; }思路简要说明虚拟头节点创建一个虚拟头节点head用temp负责向后构建结果链表最后返回head.next逐位相加由于链表是倒序存储直接从头节点开始就是从最低位开始相加进位变量 carry用carry保存上一轮产生的进位并在下一轮一开始加入sum循环条件只要l1没结束、l2没结束或者carry还有值就继续循环三、思路详解暴力思路为什么不适合如果不考虑链表特性可能会想到先把两个链表还原成数字相加后再拆成链表但这个思路有两个问题数字可能非常大链表长度可能很长转成int或long都可能溢出没有必要还原整个数字加法本来就是逐位进行的我们完全可以模拟竖式加法所以正确的方向不是把链表转成数字而是直接在链表上模拟加法竖式加法的过程我们平时做加法时是从低位开始342 465 ----- 807计算顺序是个位2 5 7十位4 6 10当前位写 0向百位进 1百位3 4 1 8而题目中链表是倒序存储的l1: 2 → 4 → 3 l2: 5 → 6 → 4这刚好对应从个位到百位的顺序因此我们只需要两个指针分别遍历l1和l2每轮把当前节点值相加即可为什么需要虚拟头节点结果链表是动态创建的。如果没有虚拟头节点就需要额外判断当前是否是第一个节点如果是第一个节点要初始化结果链表头节点如果不是第一个节点才可以执行temp.next new ListNode(...)这样代码会多出很多特殊判断所以我们先创建一个虚拟头节点ListNode temp new ListNode(-1); ListNode head temp;其中head永远指向虚拟头节点用于最后返回head.nexttemp负责移动始终指向结果链表的最后一个节点这样每次创建新节点时都可以统一写temp.next new ListNode(sum); temp temp.next;最后返回head.next跳过虚拟头节点即可进位为什么不能直接加到下一个节点这道题最容易写乱的地方就是进位假设当前两位相加大于等于 10需要给下一位加 1。一个直觉做法可能是直接把这个 1 加到结果链表的下一个节点上但问题是结果链表的下一个节点此时还没有创建比如l1: 9 l2: 9当前位相加9 9 18如果想把进位直接加到下一位直觉上可能会想这样当前已经创建的结果链表 head(-1) → 8 ↑ temp 想要把进位1加到下一位 head(-1) → 8 → ? ↑ 这里的节点还不存在也就是说此时结果链表里只有当前位节点8下一位节点还没有创建根本不存在可以加 1 的位置。如果强行去想temp.next.next一定会出问题因为temp.next可能都是 null更不用说temp.next.next而最终正确的结果应该是head(-1) → 8 → 1 返回 head.next8 → 1所以问题的本质是进位属于下一轮计算但下一轮的节点现在还没有创建这就是为什么不能直接操作链表节点来处理进位而是要用一个变量carry暂时保存下来。等下一轮循环开始时再通过sum carry把这个进位自然加进去sum 和 carry 的配合解决进位问题的关键是两个变量sum当前这一位的总和carry当前这一位产生的进位留给下一位使用每一轮循环开始时int sum carry;这一步非常关键。上一轮留下来的进位会在下一轮一开始自然加入当前位计算然后加上两个链表当前节点的值if (l1 ! null) { sum l1.val; l1 l1.next; } if (l2 ! null) { sum l2.val; l2 l2.next; }接着处理当前位和进位carry sum / 10; sum % 10;含义是sum % 10当前节点真正应该存的值sum / 10需要进到下一位的值例如sum 18当前位存18 % 10 8下一位进18 / 10 1为什么循环条件要包含 carry ! 0循环条件是while (l1 ! null || l2 ! null || carry ! 0)这三个条件分别表示l1 ! null第一个链表还有位数没加完l2 ! null第二个链表还有位数没加完carry ! 0链表都加完了但还有最后一个进位没处理最后一个条件特别重要例如l1: 9 l2: 9第一轮sum 0 9 9 18 当前位 8 carry 1此时l1 nulll2 null但carry 1所以还需要继续循环一轮sum carry 1 当前位 1 carry 0最终结果才是8 → 1如果循环条件没有carry ! 0结果就会错误地变成只有8举例说明以l1 2 → 4 → 3l2 5 → 6 → 4为例轮次l1l2carry 初始值sum当前节点值新 carry结果链表12500257707246004610017→033411348807→0→8最终结果为7 → 0 → 8表示数字 807再看一个进位到最后的例子l1 9l2 9轮次l1l2carry 初始值sum当前节点值新 carry结果链表1990188182nullnull11108→1最终结果为8 → 1时间复杂度O(max(m, n))m 和 n 分别为两个链表长度空间复杂度O(max(m, n))结果链表需要存储最终答案除结果链表外只用了常数变量