概览：
前置知识：理解链表及其基本调整 建议：做过这个题2. 两数相加的同学跳过
给你两个 非空 的链表，表示两个非负的整数
它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字
请你将两个数相加，并以相同形式返回一个表示和的链表
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
链表题目在笔试、面试中的意义就是检验coding能力如何
更难的题目会在【必备】课程里讲述
力扣2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
1
2
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1. 基本思想：模拟手算加法，从低位到高位逐位相加，处理进位。
2. 处理步骤：
- 首先检查特殊情况：如果任一链表为空，直接返回另一个
- 使用 carry 变量记录进位，初始为0
- digit1 和 digit2 分别取两个链表当前节点的值（若已到末尾则取0）
- 创建结果链表，head 为头节点，headCopy 用于追踪当前节点
3. 核心循环：
- 只要 l1 或 l2 还有节点就继续
- 计算当前位总和：sum = digit1 + digit2 + carry
- 更新进位：carry = sum / 10
- 当前位结果：sum % 10
- 第一次循环创建头节点，后续循环追加新节点
- 移动 l1 和 l2 到下一节点
4. 收尾：
- 循环结束后检查是否还有剩余进位
- 如有进位，添加到结果链表末尾
5. 返回值：
- 返回结果链表的头节点 head
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 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) {
if (l1 == null) return l2;
if (l2 == null) return l1;
int carry = 0, digit1, digit2;
ListNode head = null, cur, headCopy = null;
while (l1 != null || l2 != null) {
digit1 = l1 != null ? l1.val : 0;
digit2 = l2 != null ? l2.val : 0;
int sum = digit1 + digit2 + carry;
carry = sum / 10;
if (head == null){
head = new ListNode(sum % 10);
headCopy = head;
}else {
cur = new ListNode(sum % 10);
headCopy.next = cur;
headCopy = cur;
}
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (carry != 0) {
headCopy.next = new ListNode(carry);
}
return head;
}
}
这道题和67. 二进制求和比较类似
补充：力扣67. 二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
1
2
输入:a = "11", b = "1"
输出："100"
示例 2：
1
2
输入：a = "1010", b = "1011"
输出："10101"
提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, cn = 0, m = 0;//cn是进位，m是余数
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || cn > 0) {
int p = (i >= 0) ? a.charAt(i--) - '0' : 0;
int q = (j >= 0) ? b.charAt(j--) - '0' : 0;
sb.insert(0, (p + q + cn) % 2);
cn = (p + q + cn) / 2;
}
return sb.toString();
}
}
