链表

两数相加

中等#2Java时间 O(max(m,n))空间 O(max(m,n)),输出

题目要做什么

两条非空链表按低位在前保存两个非负整数,每个节点是一位数字。返回相同表示方式的和。

题目示例输入l1 = [2,4,3], l2 = [5,6,4]
题目示例输出[7,0,8]

01 为什么这样做

从个位起逐位相加,同时携带进位。当前结果是 sum%10,下一位进位是 sum/10。两条链都结束后,仍可能需要一个额外进位节点。

始终成立的条件

结果已完成较低位,carry 保存向下一位传递的进位。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {3        ListNode dummy = new ListNode(0), tail = dummy;4        int carry = 0;5        while (l1 != null || l2 != null || carry != 0) {6            int sum = carry + (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);7            tail.next = new ListNode(sum % 10);8            tail = tail.next;9            carry = sum / 10;10            if (l1 != null) l1 = l1.next;11            if (l2 != null) l2 = l2.next;12        }13        return dummy.next;14    }15}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索