2. 两数相加

题目：两数相加

描述

给定两个非空链表，表示两个非负整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

---

示例

示例 1:

输入: l1 = [2,4,3], l2 = [5,6,4]
输出: [7,0,8]
解释: 342 + 465 = 807

示例 2:

输入: l1 = [0], l2 = [0]
输出: [0]

示例 3:

输入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出: [8,9,9,9,0,0,0,1]

---

解题思路

关键点

1. 链表中的数字按照逆序存储，因此链表的头节点对应数字的个位。
2. 我们的目标是按位相加，处理进位，最终返回一个新的链表。
3. 进位：每一位相加时，如果和大于等于 10，就需要将进位加到下一位。
4. 链表操作：需要遍历两个链表，逐位相加并构建结果链表。

---

思路来源：模拟手动加法过程

1. 初始化：

   • 使用一个虚拟头节点来简化代码。
   • carry 记录当前位的进位，初始化为 0。
   • 使用两个指针 p1 和 p2 分别指向 l1 和 l2 的头节点。

2. 遍历两个链表：

   • 每次取 p1 和 p2 所指向的节点的值，如果某个链表已经遍历完，就认为该链表的当前节点值为 0。
   • 将两个节点的值与当前的 carry 相加，计算新的 carry 和当前位的值。
   • 将结果添加到新的链表中。

3. 处理完所有节点后：

   • 如果最后 carry 不为 0，说明还有一个进位，需要额外添加一个节点。

---

具体步骤

步骤 1：初始化虚拟头节点 dummy，以及指向该节点的指针 current，用于构建结果链表。

步骤 2：遍历两个链表：

• 取 l1 和 l2 当前位的值，并计算它们的和。
• 如果和大于等于 10，则进位为 1，否则进位为 0。
• 将当前和对 10 取余作为新节点值。

步骤 3：继续遍历链表直到两个链表都为空，同时处理进位。

步骤 4：如果 carry 为 1，说明最后还有进位，创建一个新的节点。

---

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取第一个链表
        String[] list1Values = scanner.nextLine().split(" ");
        ListNode l1 = null;
        ListNode tail1 = null;
        for (String val : list1Values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (l1 == null) {
                    l1 = newNode;
                    tail1 = newNode;
                } else {
                    tail1.next = newNode;
                    tail1 = newNode;
                }
            }
        }

        // 读取第二个链表
        String[] list2Values = scanner.nextLine().split(" ");
        ListNode l2 = null;
        ListNode tail2 = null;
        for (String val : list2Values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (l2 == null) {
                    l2 = newNode;
                    tail2 = newNode;
                } else {
                    tail2.next = newNode;
                    tail2 = newNode;
                }
            }
        }

        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);

        // 输出结果链表
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 创建一个虚拟头节点
        ListNode current = dummy; // 当前链表节点
        int carry = 0; // 进位，初始为0

        // 遍历 l1 和 l2，同时处理进位
        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); // 当前节点的值是 sum 对 10 取余

            current = current.next; // 移动 current 指针
            if (l1 != null) l1 = l1.next; // 移动 l1 指针
            if (l2 != null) l2 = l2.next; // 移动 l2 指针
        }

        return dummy.next; // 返回结果链表
    }
}

// ListNode 类定义
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

---

代码解析

示例：l1 = [2,4,3] 和 l2 = [5,6,4]

1. 第一轮相加：

   • l1 的值为 2，l2 的值为 5，进位为 0，和为 7，进位为 0。
   • 新链表为 [7]。

2. 第二轮相加：

   • l1 的值为 4，l2 的值为 6，进位为 0，和为 10，进位为 1。
   • 新链表为 [7, 0]。

3. 第三轮相加：

   • l1 的值为 3，l2 的值为 4，进位为 1，和为 8，进位为 0。
   • 新链表为 [7, 0, 8]。

最终结果是 [7, 0, 8]，即 342 + 465 = 807。

---

时间复杂度分析

• 每个链表最多遍历一次，处理每个节点的时间复杂度为 O(1)。
• 因此，整个过程的时间复杂度为 O(n)，其中 n 是链表的长度。

空间复杂度分析

• 新链表的长度与输入链表的长度相同，因此空间复杂度为 O(n)。

---

总结

• 核心思路：模拟手动加法过程，逐位相加并处理进位。
• 为何选择这种方法？
  • 使用两个指针遍历链表，确保时间复杂度为 O(n)，空间复杂度为 O(n)，符合题目要求。
• 适用场景：适用于链表表示的大数加法，尤其是无法直接对整数进行计算的情况下。