LeetCode 2. 两数相加

Categories:

Tags:

题目描述
思路分析
1. 解法一：模拟进位（推荐）
相似题目

题目描述

✅ 2. 两数相加

思路分析

解法一：模拟进位（推荐）

核心思路：

链表逆序存储（个位在头部），天然符合竖式加法从低位到高位的顺序，可直接同步遍历两链表。

创建虚拟头结点 dummy，cur 指向结果链表尾部，carry 记录进位，初始为 0。

循环条件为 l1 != null || l2 != null || carry > 0，三者任一非零则继续迭代。

每轮计算 sum = carry + l1.val（若存在）+ l2.val（若存在），新节点值为 sum % 10，进位更新为 sum / 10。

终止条件的关键：不能只判断两链表均为空，还必须等 carry == 0。反例：[5] + [5] = [0, 1]，两链表走完后仍有进位 1 未处理。

复杂度分析：

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

空间复杂度：O(max(m, n))，结果链表最多 max(m, n) + 1 个节点

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 sum = carry;
            // 取 l1 当前位的值
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            // 取 l2 当前位的值
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            // 当前位结果挂到结果链表
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            // 更新进位
            carry = sum / 10;
        }
        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 虚拟头节点，简化边界处理
    dummy := &ListNode{}
    cur := dummy
    carry := 0
    // 任意链表非空或仍有进位时继续迭代
    for l1 != nil || l2 != nil || carry > 0 {
        total := carry
        // 取 l1 当前位的值
        if l1 != nil {
            total += l1.Val
            l1 = l1.Next
        }
        // 取 l2 当前位的值
        if l2 != nil {
            total += l2.Val
            l2 = l2.Next
        }
        // 当前位结果挂到结果链表
        cur.Next = &ListNode{Val: total % 10}
        cur = cur.Next
        // 更新进位
        carry = total / 10
    }
    return dummy.Next
}

相似题目

题目	难度	考察点
445. 两数相加 II	中等	链表正序存储，需反转或用栈
67. 二进制求和	简单	字符串模拟进位
415. 字符串相加	简单	字符串模拟竖式加法
43. 字符串相乘	中等	字符串模拟乘法
989. 数组形式的整数加法	简单	数组逐位相加进位
369. 给单链表加一	中等	链表进位操作

本文作者: HGNULB

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