LeetCode LCR 025. 两数相加 II

Categories:

题目描述
思路分析
1. 解法一：栈（推荐）
2. 解法二：反转链表
相似题目

题目描述

✅ LCR 025. 两数相加 II

思路分析

解法一：栈（推荐）

核心思路：

链表从高位到低位存储，直接相加需要对齐末位，用栈可以天然实现从低位到高位的遍历

分别将两条链表的所有节点值压栈，然后同步弹出栈顶元素相加，处理进位，并用头插法构建结果链表

头插法保证结果链表从高位到低位排列，与题目要求一致

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为两条链表的长度

空间复杂度：O(m + n)，两个栈的空间

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 分别将两条链表的节点值压栈
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        ListNode pre = null;
        int carry = 0;
        // 同步弹出栈顶相加，处理进位，用头插法构建结果链表
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int sum = carry;
            if (!stack1.isEmpty()) {
                sum += stack1.pop();
            }
            if (!stack2.isEmpty()) {
                sum += stack2.pop();
            }
            carry = sum / 10;
            ListNode cur = new ListNode(sum % 10);
            // 头插法：新节点指向当前头节点，保证高位在前
            cur.next = pre;
            pre = cur;
        }
        return pre;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 分别将两条链表的节点值压栈
    stack1, stack2 := []int{}, []int{}
    for l1 != nil {
        stack1 = append(stack1, l1.Val)
        l1 = l1.Next
    }
    for l2 != nil {
        stack2 = append(stack2, l2.Val)
        l2 = l2.Next
    }

    var pre *ListNode
    carry := 0
    // 同步弹出栈顶相加，处理进位，用头插法构建结果链表
    for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
        sum := carry
        if len(stack1) > 0 {
            sum += stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }
        if len(stack2) > 0 {
            sum += stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }
        carry = sum / 10
        cur := &ListNode{Val: sum % 10}
        // 头插法：新节点指向当前头节点，保证高位在前
        cur.Next = pre
        pre = cur
    }
    return pre
}

解法二：反转链表

核心思路：

先将两条链表分别反转，使其从低位到高位排列，等价于「两数相加 I」

按位相加并处理进位，同样用头插法构建结果，最终结果自然是高位在前

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为两条链表的长度

空间复杂度：O(1)，只使用常数额外空间（不含输出链表）

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 反转两条链表，使低位在前
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode pre = null;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            // 头插法构建结果链表
            ListNode cur = new ListNode(sum % 10);
            cur.next = pre;
            pre = cur;
        }
        return pre;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 反转两条链表，使低位在前
    l1 = reverseList(l1)
    l2 = reverseList(l2)

    var pre *ListNode
    carry := 0
    for l1 != nil || l2 != nil || carry > 0 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        carry = sum / 10
        // 头插法构建结果链表
        cur := &ListNode{Val: sum % 10}
        cur.Next = pre
        pre = cur
    }
    return pre
}

// reverseList 反转链表
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

相似题目

题目	难度	考察点
2. 两数相加	中等	链表 / 进位处理
67. 二进制求和	简单	字符串 / 进位处理
43. 字符串相乘	中等	字符串 / 逐位相乘
369. 给单链表加一	中等	链表 / 栈 / 进位
989. 数组形式的整数加法	简单	数组 / 进位处理
415. 字符串相加	简单	字符串 / 进位处理

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/47669840