#P4045. 两数相加
-
ID: 2287
Tried: 66
Accepted: 21
Difficulty: 5
两数相加
题目描述
给定两个非空链表 L1 和 L2，表示两个非负整数。
它们的每位数字按逆序存储，每个节点只能存储一位数字。
请计算它们的和，并以相同的逆序链表形式返回结果。
输入描述
输入包含多组测试数据。
第一行输入一个整数 T（1≤T≤100），表示测试用例的数量。
对于每个测试用例：
- 第一行输入一个整数
n（1≤n≤100），表示链表L1的节点数。 - 第二行输入
n个整数（0≤Node.val≤9），表示L1的各位数字，按逆序存储。 - 第三行输入一个整数
m（1≤m≤100），表示链表L2的节点数。 - 第四行输入
m个整数（0≤Node.val≤9），表示L2的各位数字，按逆序存储。
输出描述
对于每个测试用例，输出一行，表示两个链表相加后的结果，格式为：
- 按逆序存储的和，各位数字用空格分隔。
- 如果结果为 0，仅输出
0，不输出额外空格或换行。
样例输入
3
3
2 4 3
3
5 6 4
1
0
1
0
7
9 9 9 9 9 9 9
4
9 9 9 9
样例输出
7 0 8
0
8 9 9 9 0 0 0 1
提示
- 每个链表的长度在 [1, 100] 之间。
- 每个节点的值范围是 [0, 9]。
- 输入保证数字没有前导零（即不会出现
0 1 2这样的情况）。
解题思路
- 利用链表逆序存储的特点，从低位到高位依次相加。
- 使用进位 (
carry) 变量 来存储进位值，确保高位正确。 - 遍历
L1和L2：- 取出
L1和L2当前位的值（如果某个链表已遍历完，则补 0）。 - 计算
sum = val1 + val2 + carry，更新carry = sum // 10，当前位sum % 10作为新节点存入结果链表。 - 继续遍历，直到
L1和L2都遍历完，且carry == 0。
- 取出
- 构建结果链表，输出时用空格分隔节点值，0 仅输出一次。
时间复杂度 & 空间复杂度
- 时间复杂度：O(max(n, m))，
n和m分别是L1和L2的长度，最多遍历一次。 - 空间复杂度：O(max(n, m))，新建链表存储相加后的结果。
Python 代码
import sys
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
""" 计算两个逆序存储的链表之和 """
dummy = ListNode(-1) # 创建虚拟头节点
current = dummy # 结果链表的指针
carry = 0 # 进位变量
while l1 or l2 or carry:
val1 = l1.val if l1 else 0 # 获取 L1 当前位
val2 = l2.val if l2 else 0 # 获取 L2 当前位
total = val1 + val2 + carry # 计算当前位相加的值
carry = total // 10 # 计算进位
current.next = ListNode(total % 10) # 创建新节点存入当前位
current = current.next # 移动指针
# 移动 L1 和 L2 指针
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next # 返回计算结果链表的头节点
def build_linked_list(lst):
""" 通过列表构建链表 """
if not lst:
return None
head = ListNode(lst[0])
current = head
for val in lst[1:]:
current.next = ListNode(val)
current = current.next
return head
def linked_list_to_list(head):
""" 将链表转换为列表 """
result = []
while head:
result.append(head.val)
head = head.next
return result
# 读取输入
l1_size = int(sys.stdin.readline().strip()) # 读取 L1 长度
l1 = list(map(int, sys.stdin.readline().split())) if l1_size > 0 else [] # 读取 L1 数据
l2_size = int(sys.stdin.readline().strip()) # 读取 L2 长度
l2 = list(map(int, sys.stdin.readline().split())) if l2_size > 0 else [] # 读取 L2 数据
# 计算加法
l1_head = build_linked_list(l1) # 构建 L1 链表
l2_head = build_linked_list(l2) # 构建 L2 链表
result_head = addTwoNumbers(l1_head, l2_head) # 计算两个链表的和
result_list = linked_list_to_list(result_head) # 转换回列表
# 输出结果（空格分隔）
print(" ".join(map(str, result_list)))
Java 代码
import java.util.*;
class ListNode {
int val; // 存储节点的值
ListNode next; // 指向下一个节点的指针
// 构造函数，初始化节点值
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int T = scanner.nextInt(); // 读取测试用例数量
for (int t = 0; t < T; t++) {
int n = scanner.nextInt(); // 读取 L1 长度
ListNode l1 = (n > 0) ? buildLinkedList(scanner, n) : null;
int m = scanner.nextInt(); // 读取 L2 长度
ListNode l2 = (m > 0) ? buildLinkedList(scanner, m) : null;
ListNode result = addTwoNumbers(l1, l2); // 计算两个链表的和
printLinkedList(result); // 输出结果
}
scanner.close();
}
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1); // 创建虚拟头节点，便于处理链表
ListNode current = dummy; // 结果链表的指针
int carry = 0; // 进位变量
// 遍历 L1 和 L2，直到两个链表都遍历完，且进位为 0
while (l1 != null || l2 != null || carry > 0) {
int val1 = (l1 != null) ? l1.val : 0; // 获取 L1 当前位值
int val2 = (l2 != null) ? l2.val : 0; // 获取 L2 当前位值
int sum = val1 + val2 + carry; // 计算当前位相加的值
carry = sum / 10; // 计算进位
current.next = new ListNode(sum % 10); // 存储当前位结果
current = current.next; // 移动指针
if (l1 != null) l1 = l1.next; // 移动 L1 指针
if (l2 != null) l2 = l2.next; // 移动 L2 指针
}
return dummy.next; // 返回计算结果链表的头节点
}
public static ListNode buildLinkedList(Scanner scanner, int size) {
ListNode head = new ListNode(scanner.nextInt()); // 读取第一个节点
ListNode current = head;
for (int i = 1; i < size; i++) {
current.next = new ListNode(scanner.nextInt()); // 读取后续节点
current = current.next;
}
return head; // 返回链表头
}
public static void printLinkedList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val);
if (current.next != null) System.out.print(" "); // 空格分隔
current = current.next;
}
System.out.println(); // 输出换行
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val; // 存储节点的值
ListNode* next; // 指向下一个节点的指针
// 构造函数，初始化节点值
ListNode(int x) : val(x), next(nullptr) {}
};
// 计算两个逆序存储的链表之和
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(-1); // 创建虚拟头节点
ListNode* current = &dummy; // 结果链表的指针
int carry = 0; // 进位变量
// 遍历 L1 和 L2，直到两个链表都遍历完，且进位为 0
while (l1 || l2 || carry) {
int val1 = (l1) ? l1->val : 0; // 获取 L1 当前位值
int val2 = (l2) ? l2->val : 0; // 获取 L2 当前位值
int sum = val1 + val2 + carry; // 计算当前位相加的值
carry = sum / 10; // 计算进位
current->next = new ListNode(sum % 10); // 存储当前位结果
current = current->next; // 移动指针
if (l1) l1 = l1->next; // 移动 L1 指针
if (l2) l2 = l2->next; // 移动 L2 指针
}
return dummy.next; // 返回计算结果链表的头节点
}
// 通过数组构建链表
ListNode* buildLinkedList(vector<int>& lst) {
if (lst.empty()) return nullptr;
ListNode* head = new ListNode(lst[0]); // 创建头节点
ListNode* current = head;
for (size_t i = 1; i < lst.size(); i++) {
current->next = new ListNode(lst[i]); // 添加新节点
current = current->next;
}
return head; // 返回链表头部
}
// 打印链表
void printLinkedList(ListNode* head) {
while (head) {
cout << head->val;
if (head->next) cout << " "; // 空格分隔
head = head->next;
}
cout << endl; // 输出换行
}
int main() {
int T;
cin >> T; // 读取测试用例数量
while (T--) {
int n, m;
cin >> n; // 读取 L1 长度
vector<int> lst1(n);
for (int i = 0; i < n; i++) {
cin >> lst1[i]; // 读取 L1 数据
}
cin >> m; // 读取 L2 长度
vector<int> lst2(m);
for (int i = 0; i < m; i++) {
cin >> lst2[i]; // 读取 L2 数据
}
ListNode* l1 = buildLinkedList(lst1); // 构建 L1 链表
ListNode* l2 = buildLinkedList(lst2); // 构建 L2 链表
ListNode* result = addTwoNumbers(l1, l2); // 计算链表和
printLinkedList(result); // 输出结果
}
return 0;
}