题目描述
给出两个非空链表用来表示两个非负整数
其中它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字
如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和
可以假设除了数字 0 之外，这两个数都不会以 0 开头
数据结构
- 链表
算法思维
- 遍历、数学思维
解题要点
- 大数相加，不能出现越界问题：链表的扩展性
- 数学思维的应用：遇到涉及数字的问题时，首先应该想到能否利用数学方法达到目标
- 链表的特点：
• 由一系列节点组成，在运行时动态生成
• 节点在内存中的存储位置是非连续、非顺序的
• 每个节点包括：数据域 + 指针域
• 数据存储不要求连续空间，不限制容量
• 数据的逻辑顺序通过指针链接次序实现
• 从链表头部依次访问后面的节点
• 在链表表头插入数据的时间复杂度是O(1)
解题步骤
一. Comprehend 理解题意
题目主干要求
- 一个链表表示一个整数
- 每个节点存储一个数字
- 整数相加 == 链表相加
- 返回值为链表，表示的两数之和
细节问题
- 两个链表都是非空的
- 两个非负整数
- 两个数字都不会以0开头
- 数字逆序排列，第一个节点表示整数的最低位
- 考点：题目没有明确整数范围，意味着算法需要适用于任意大小的整数
解题思路
- 解法一：分别将链表转成数字，再相加
- 解法二：直接将对应位置数字相加
二. Choose 选择数据结构与算法
- 解法一：链表转换为整数，再相加
数据结构：链表
算法思维：遍历
时间复杂度：O(m+n) -- 两个链表的遍历；O(max(m,n)) -- 新链表的尾插
总时间复杂度：O(m+n+max(m,n)) ≈ O(m+n)
空间复杂度：O(max(m,n)) -- 一个新链表的内存空间，长度取决于两数之和的位数
三. Code 编码实现基本解法
解法一：转换整数，再相加 -- 不可用！！
- 遍历两个链表使用数学思维分别将他们转成整数
- 对两个整数进行求和得到 sum
- 将 sum 按照数学思维再转成链表
/**
* 暴⼒解法：存在的问题：使⽤long也会存在溢出
* 解决办法：java.math.BigInteger
* 该类在leetcode默认环境没有导⼊，所以使⽤全类名编写
*
* @param l1
* @param l2
* @return
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//把链表转成数字，注意次序为逆序
java.math.BigInteger l1Value = java.math.BigInteger.valueOf(0);
int digit = 0;
while(l1 != null) {
java.math.BigInteger carry = java.math.BigInteger.valueOf(10).pow(digit);
l1Value = l1Value.add(carry.multiply(java.math.BigInteger.valueOf(l1.val)));
digit++;
l1 = l1.next;
}
java.math.BigInteger l2Value = java.math.BigInteger.valueOf(0);
digit = 0;
while(l2 != null) {
java.math.BigInteger carry = java.math.BigInteger.valueOf(10).pow(digit);
l2Value = l2Value.add(carry.multiply(java.math.BigInteger.valueOf(l2.val)));
digit++;
l2 = l2.next;
}
ListNode head = new ListNode();
ListNode cur = head;
//数字相加，然后再转成链表
java.math.BigInteger sum = l1Value.add(l2Value);
if(sum.compareTo(java.math.BigInteger.valueOf(0)) == 0) {
head = new ListNode(0);
return head;
}
while(sum.compareTo(java.math.BigInteger.valueOf(0)) > 0) {
int val = sum.mod(java.math.BigInteger.valueOf(10)).intValue();
sum = sum.divide(java.math.BigInteger.valueOf(10));
ListNode node = new ListNode((int) val);
cur.next = node;
cur = cur.next;
}
return head.next;
}
}
边界问题
- 链表转整数时，next == null 结尾
- 整数转链表，处理完最高位：value == 0
致命问题
- 题目没有明确整数范围
int 溢出可以用 long，long 溢出呢？
使用 BigInteger 可以实现，但效率很低
四. Consider 思考更优解
改变算法思维：链表转整数效率低且容易越界，有没有办法跳过这个步骤呢？
- 解法二：链表对应节点相加
数据结构：链表
算法思维：遍历、数学思维
时间复杂度：O(max(m,n)) -- 一次链表遍历，循环次数由较长的链表的长度决定
空间复杂度：O(max(m,n)) -- 一个新链表的内存空间
五. Code 编码实现最优解
解法二：对应节点相加
- 遍历两个链表
- 对应位置的节点数值相加
- 将结果插入新链表尾部
- 若大于10，则进位，将进位加到下个节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode head = new ListNode();
ListNode curr = head;
//遍历两个链表，逐位相加，计算进位
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
carry = val1 + val2 + carry;
curr.next = new ListNode(carry % 10, null);
carry /= 10;
l1 = l1 == null ? l1 : l1.next;
l2 = l2 == null ? l2 : l2.next;
curr = curr.next;
}
//判断最终是否还有进位
if (carry > 0) curr.next = new ListNode(1);
return head.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
}
执行耗时：执行耗时:2 ms，击败了 99.84% 的Java用户
内存消耗：38.5 MB，击败了 93.00% 的Java用户
边界问题
- 两个链表边界：当前节点 == null
细节问题
- 两个链表长度不一致，短链表高位视为 0
- 链表最高位发生进位，结果链表需要增加一个节点存放进位数字
六. Change 变形与延伸
- 两数相减如何实现（进位变借位）？
