企业官网建设流程全解析

这道题是 LeetCode 2. 两数相加 的进阶版，核心难点在于链表高位在前，无法直接从个位开始相加。

题目简述

给你两个 非空 链表，表示两个非负整数，数字以 逆序 存储（最高位在链表头部）。请将两数相加，并以相同形式返回一个表示和的链表。

核心思路

由于加法需要从低位（个位）开始，而链表是高位在前，因此需要反转链表或借助栈来实现逆序处理。这里推荐使用 栈，思路更清晰：

1. 将两个链表的值分别压入两个栈。
2. 依次弹出栈顶元素相加，维护进位 carry。
3. 使用 头插法 构建结果链表（因为先算出的是低位，需要放在链表尾部）。

Java 实现

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque stack1 = new ArrayDeque<>();
Deque stack2 = new ArrayDeque<>();

// 将链表值压入栈 while (l1 != null) { stack1.push(l1.val); l1 = l1.next; } while (l2 != null) { stack2.push(l2.val); l2 = l2.next; } int carry = 0; ListNode dummy = new ListNode(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; int digit = sum % 10; // 头插法：新节点插入到 dummy 后面 ListNode node = new ListNode(digit); node.next = dummy.next; dummy.next = node; } return dummy.next; }

}

复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 分别为两个链表的长度。
• 空间复杂度：O(m + n)，用于存储两个栈。

面试延伸

• 如果不允许修改原链表：栈方案是最佳选择。
• 如果允许修改原链表：可以先反转两个链表，按 LeetCode 2 的方式相加，再反转结果链表，空间复杂度可降为 O(1)（不计输出链表）。
• 头插法技巧：因为栈弹出的是低位，而结果链表需要高位在前，所以每次新节点都插到头部。

需要我接着为你讲解 LeetCode 2. 两数相加 的对比实现吗？