2. 两数相加

力扣题目链接 (opens new window)

题目描述

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

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

你可以假设除了数字 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, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

这道题本质上就是模拟小学学的加法竖式运算。

两个数相加，从低位到高位逐位相加，还要处理进位。

好在题目已经帮我们把数字逆序存储了，链表从头到尾就是从低位到高位，正好方便我们遍历。

思路就是：

1. 同时遍历两个链表，逐位相加
2. 用一个变量carry记录进位（0或1）
3. 每次计算sum = l1.val + l2.val + carry
4. 当前位的值是sum % 10，进位是sum / 10
5. 创建新节点存储当前位的值，接到结果链表后面

需要注意的细节：

• 两个链表长度可能不同，遍历时要判断是否为空
• 最后可能还有进位，比如99 + 1 = 100，最后要单独创建一个节点
• 用一个**哨兵节点（dummy head）**简化链表操作，最后返回dummy->next

模拟过程

以 l1 = [2,4,3], l2 = [5,6,4] 为例（表示 342 + 465 = 807）：

逐位相加，处理进位：

• 第1位：2 + 5 = 7，carry = 0
• 第2位：4 + 6 = 10，结果 0，carry = 1（进位）
• 第3位：3 + 4 + 1(carry) = 8，carry = 0

最终结果链表：7 → 0 → 8

特殊情况：如果最后还有进位（如 9→9→9 + 1），需要单独创建新节点。

解题代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);  // 哨兵节点
        ListNode* cur = dummy;
        int carry = 0;  // 进位
        
        // 同时遍历两个链表
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int val1 = (l1 != nullptr) ? l1->val : 0;
            int val2 = (l2 != nullptr) ? l2->val : 0;
            
            int sum = val1 + val2 + carry;
            carry = sum / 10;  // 计算进位
            
            cur->next = new ListNode(sum % 10);  // 创建新节点
            cur = cur->next;
            
            // 移动指针
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        
        return dummy->next;
    }
};

复杂度分析

• 时间复杂度：O(max(m, n))，其中m和n是两个链表的长度
• 空间复杂度：O(max(m, n))，结果链表的长度

其他语言

Python3

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)  # 哨兵节点
        cur = dummy
        carry = 0  # 进位
        
        # 同时遍历两个链表
        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            
            sum_val = val1 + val2 + carry
            carry = sum_val // 10  # 计算进位
            
            cur.next = ListNode(sum_val % 10)  # 创建新节点
            cur = cur.next
            
            # 移动指针
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        
        return dummy.next

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);  // 哨兵节点
        ListNode cur = dummy;
        int carry = 0;  // 进位
        
        // 同时遍历两个链表
        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            
            int sum = val1 + val2 + carry;
            carry = sum / 10;  // 计算进位
            
            cur.next = new ListNode(sum % 10);  // 创建新节点
            cur = cur.next;
            
            // 移动指针
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        return dummy.next;
    }
}

Go

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}  // 哨兵节点
    cur := dummy
    carry := 0  // 进位
    
    // 同时遍历两个链表
    for l1 != nil || l2 != nil || carry != 0 {
        val1, val2 := 0, 0
        if l1 != nil {
            val1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            val2 = l2.Val
            l2 = l2.Next
        }
        
        sum := val1 + val2 + carry
        carry = sum / 10  // 计算进位
        
        cur.Next = &ListNode{Val: sum % 10}  // 创建新节点
        cur = cur.Next
    }
    
    return dummy.Next
}

JavaScript

var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(0);  // 哨兵节点
    let cur = dummy;
    let carry = 0;  // 进位
    
    // 同时遍历两个链表
    while (l1 !== null || l2 !== null || carry !== 0) {
        let val1 = (l1 !== null) ? l1.val : 0;
        let val2 = (l2 !== null) ? l2.val : 0;
        
        let sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10);  // 计算进位
        
        cur.next = new ListNode(sum % 10);  // 创建新节点
        cur = cur.next;
        
        // 移动指针
        if (l1 !== null) l1 = l1.next;
        if (l2 !== null) l2 = l2.next;
    }
    
    return dummy.next;
};

与代码随想录联系

这道题是链表的经典题目，考察链表的基本操作和模拟能力。

我在代码随想录链表章节里，详细讲解过**哨兵节点（dummy head）**的技巧，可以大大简化链表操作。

录友们可以看一下代码随想录链表章节，特别是203.移除链表元素，那道题详细讲解了哨兵节点的妙用。

本题的关键点有两个：

1. 哨兵节点简化链表操作
2. 进位处理，注意最后可能还有进位

另外，这道题链表是逆序存储的，如果是正序存储（从高位到低位），就需要先反转链表或者用栈来处理了。