解题思路

1. 利用链表逆序存储的特点，从低位到高位依次相加。
2. 使用进位 (carry) 变量 来存储进位值，确保高位正确。
3. 遍历 L1 和 L2：
   • 取出 L1 和 L2 当前位的值（如果某个链表已遍历完，则补 0）。
   • 计算 sum = val1 + val2 + carry，更新 carry = sum // 10，当前位 sum % 10 作为新节点存入结果链表。
   • 继续遍历，直到 L1 和 L2 都遍历完，且 carry == 0。
4. 构建结果链表，输出时用空格分隔节点值，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;
}

Leetcode 28.两数相加-原题链接

题目描述

给定两个非空链表 L1 和 L2，表示两个非负整数。
它们的每位数字按逆序存储，每个节点只能存储一位数字。

请计算它们的和，并以相同的逆序链表形式返回结果。

输入描述

输入包含多组测试数据。

第一行输入一个整数 T（$1 \leq T \leq 100$），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个整数 n（$1 \leq n \leq 100$），表示链表 L1 的节点数。
• 第二行输入 n 个整数（$0 \leq Node.val \leq 9$），表示 L1 的各位数字，按逆序存储。
• 第三行输入一个整数 m（$1 \leq m \leq 100$），表示链表 L2 的节点数。
• 第四行输入 m 个整数（$0 \leq Node.val \leq 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 这样的情况）。