2 两数相加

一、题目

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

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

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

二、题解

思路： 由于数字按低位在前的逆序存储，可以从两条链表的头节点开始逐位相加，正好模拟竖式加法。设进位 carry，每一位的和为 l1.val + l2.val + carry，当前位取 sum % 10 新建结点接到结果链表尾部，进位更新为 sum / 10；某条链表先走完时用 0 补齐。使用哑结点 pre 简化头结点处理。循环结束后若仍有进位，再补一个值为 1 的结点，最后返回 pre.next。

/**
 * 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) {
        // 创建一个虚拟头节点（哨兵节点），简化边界情况处理
        // pre 始终指向结果链表的头节点前一位，用于最后返回完整链表
        ListNode pre = new ListNode(0);

        // cur 是当前操作的节点，用于逐个构建结果链表
        ListNode cur = pre;

        // carry 表示进位，初始为 0
        // 例如 7 + 8 = 15，carry = 1，当前位保留 5
        int carry = 0;

        // 循环条件：只要 l1 或 l2 任一链表还有节点，就继续处理
        // （因为两个链表长度可能不同）
        while (l1 != null || l2 != null) {
            // 如果 l1 当前节点为空（l1 更短），用 0 补齐，不影响求和
            int x = (l1 == null) ? 0 : l1.val;

            // 同理，如果 l2 当前节点为空，用 0 补齐
            int y = (l2 == null) ? 0 : l2.val;

            // 当前位的总和 = l1 对应位 + l2 对应位 + 上一位的进位
            int sum = x + y + carry;

            // 计算新的进位：整数除以 10，例如 15 / 10 = 1
            carry = sum / 10;

            // 当前位只保留个位数：例如 15 % 10 = 5
            sum = sum % 10;

            // 将计算出的当前位创建为新节点，接到结果链表末尾
            cur.next = new ListNode(sum);

            // cur 指针后移，准备处理下一位
            cur = cur.next;

            // l1 指针后移（如果还有节点的话）
            if (l1 != null) {
                l1 = l1.next;
            }

            // l2 指针后移（如果还有节点的话）
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // 循环结束后，检查是否还有剩余的进位
        // 例如 5 + 5 = 10，最后一位会产生进位 1，需要额外添加一个节点
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }

        // 返回虚拟头节点的下一个节点，即真正的结果链表头
        return pre.next;
    }
}

时间复杂度：O(max⁡(m,n))O(\max(m,n))

空间复杂度：O(max⁡(m,n))O(\max(m,n))

评论