Medium

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例 1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例 2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例 3：

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

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

进阶： 如果输入链表不能翻转该如何解决？

解题思路

这道题是 LeetCode 2 题"两数相加"的变形，区别在于数字的高位在链表的头部而不是尾部。

解法分析

方法一：栈解法（推荐）

由于高位在链表头部，我们需要从低位开始计算，但链表只能从头遍历。使用栈可以很好地解决这个问题：

  1. 分别将两个链表的所有节点值压入两个栈中
  2. 从栈顶开始弹出元素相加（相当于从个位开始计算）
  3. 处理进位，构建结果链表
  4. 采用头插法构建结果链表，确保高位在前

方法二：翻转链表法

先翻转两个输入链表，然后按照原始的两数相加方法计算，最后再翻转结果。但这种方法修改了输入，在实际场景中可能不合适。

方法三：递归法

通过递归先到达链表末尾，然后在回溯过程中处理加法和进位。但实现较复杂且空间开销大。

栈解法是最直观且不修改输入的方案，时间复杂度和空间复杂度都是最优的。

代码实现

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        
        // 将两个链表的值分别压入栈中
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        
        ListNode* result = nullptr;
        int carry = 0;
        
        // 从栈顶开始相加（从个位开始）
        while (!s1.empty() || !s2.empty() || carry) {
            int sum = carry;
            if (!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }
            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }
            
            carry = sum / 10;
            // 头插法构建结果链表
            ListNode* newNode = new ListNode(sum % 10);
            newNode->next = result;
            result = newNode;
        }
        
        return result;
    }
};

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        s1, s2 = [], []
        
        # 将两个链表的值分别压入栈中
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        
        result = None
        carry = 0
        
        # 从栈顶开始相加（从个位开始）
        while s1 or s2 or carry:
            sum_val = carry
            if s1:
                sum_val += s1.pop()
            if s2:
                sum_val += s2.pop()
            
            carry = sum_val // 10
            # 头插法构建结果链表
            new_node = ListNode(sum_val % 10)
            new_node.next = result
            result = new_node
        
        return result

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        Stack<int> s1 = new Stack<int>();
        Stack<int> s2 = new Stack<int>();
        
        // 将两个链表的值分别压入栈中
        while (l1 != null) {
            s1.Push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            s2.Push(l2.val);
            l2 = l2.next;
        }
        
        ListNode result = null;
        int carry = 0;
        
        // 从栈顶开始相加（从个位开始）
        while (s1.Count > 0 || s2.Count > 0 || carry > 0) {
            int sum = carry;
            if (s1.Count > 0) {
                sum += s1.Pop();
            }
            if (s2.Count > 0) {
                sum += s2.Pop();
            }
            
            carry = sum / 10;
            // 头插法构建结果链表
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = result;
            result = newNode;
        }
        
        return result;
    }
}

var addTwoNumbers = function(l1, l2) {
    const s1 = [], s2 = [];
    
    // 将两个链表的值分别压入栈中
    while (l1) {
        s1.push(l1.val);
        l1 = l1.next;
    }
    while (l2) {
        s2.push(l2.val);
        l2 = l2.next;
    }
    
    let result = null;
    let carry = 0;
    
    // 从栈顶开始相加（从个位开始）
    while (s1.length > 0 || s2.length > 0 || carry > 0) {
        let sum = carry;
        if (s1.length > 0) {
            sum += s1.pop();
        }
        if (s2.length > 0) {
            sum += s2.pop();
        }
        
        carry = Math.floor(sum / 10);
        // 头插法构建结果链表
        const newNode = new ListNode(sum % 10);
        newNode.next = result;
        result = newNode;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈解法
时间复杂度O(m + n)
空间复杂度O(m + n)

其中 m 和 n 分别是两个链表的长度。时间复杂度主要来自遍历两个链表和栈操作，空间复杂度主要来自两个辅助栈的存储开销。

相关题目