LeetCode 面试题 02.05. 链表求和

2025-12-15 HGNULB 约 7 分钟

文章信息 14 个分类 3 个标签

分类

LeetCode CodeTop 中等已解决已掌握 20-50 程序员面试金典（第 6 版）腾讯字节微软美团小米百度滴滴

题目描述

✅ 面试题 02.05. 链表求和

题意分析

两个链表各表示一个非负整数，每个节点只保存一位。基础题按低位在前存储，头节点就是个位；求和后也要按低位在前返回结果链表，不能把整条链先转换为固定宽度整数。

两条链长度可以不同，结果还可能因最高位进位而多一个节点。题面进阶改为高位在前存储，输出也要高位在前，下面分别说明两种顺序的处理。

解法：逐位相加模拟进位

核心思路

[!blue]

基础题的链表从头到尾恰好是低位到高位，与竖式加法的进位方向一致。因此两个指针同步向后读取，用 carry 保存已处理低位传来的进位即可。

每轮令 sum = 当前两位之和 + carry。十进制下 sum % 10 是本位，sum / 10 是交给下一位的进位；数位最大为九，进位只会为零或一。已经处理的低位无需再修改，因为更高位不会反向影响它们。

某条链提前耗尽后，该侧按零参与，另一条链继续读取。循环要持续到两条链都耗尽且进位也为零，才能保留可能新增的最高位。

当前生成的位由低到高，正好符合基础题输出顺序，因此用 tail 向结果尾部追加新节点。哑节点统一首节点与后续节点的连接，返回 dummy.next；输入节点只被读取，不改变原有连接。

解题步骤

创建结果哑节点和尾指针，令 carry = 0。

当 l1、l2 或进位任一仍有内容时继续，先用旧进位初始化本轮 sum。

两条非空链各取当前数位加入 sum，并将对应指针后移。

将值为 sum % 10 的新节点接到结果尾部，令 carry = sum / 10。

返回 dummy.next，不返回哑节点本身。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        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;
            }

            // 当前节点保存个位，十位作为下一轮进位。
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }

        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    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
        }

        // 结果链表同样按逆序存储，直接尾插当前位。
        tail.Next = &ListNode{Val: sum % 10}
        tail = tail.Next
        carry = sum / 10
    }
    return dummy.Next
}

复杂度分析

时间复杂度：$O(\max(m,n))$。每轮至少消费一个输入节点，最多再执行一轮处理最终进位。

空间复杂度：$O(1)$ 额外空间；返回链表占 $O(\max(m,n))$ 空间。

关键点总结

[!green]

逆序存储使低位先到，正好可以一趟模拟竖式加法。

循环条件必须覆盖两个输入和最终进位，长度不等也无需预处理。

sum % 10 是当前位，sum / 10 是下一位进位，两者必须来自同一个 sum。

哑节点只负责简化尾插，真正结果从 dummy.next 开始。

进阶：正序链表用栈从低位相加

核心思路

[!blue]

题面进阶把最高位放在链表头部，但进位仍然必须从最低位开始处理。先分别遍历两条链，将数位压入两个栈，栈顶就对应最低的未处理数位，出栈顺序恢复为加法需要的低位到高位。

每轮弹出两边仍存在的数位，与进位相加；某个栈为空则该侧按零处理。计算出的 sum % 10 是当前结果位，sum / 10 继续传向更高位，输入耗尽后仍需处理最后的进位。

结果也要求高位在前，而生成顺序是低位在前，所以每生成一个节点就插到结果头部。新节点恰好比已经生成的整段结果高一位，头插后顺序自然正确，不需要再次反转，也不会修改两条输入链表。

解题步骤

分别遍历两条输入链，将每个节点的值压入对应栈。

初始化结果头节点为空、进位为零。

当任一栈非空或还有进位时继续，弹出有效数位，求和后生成当前位节点。

将新节点指向原结果头，更新结果头与进位；最终返回结果头节点。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> first = new ArrayDeque<>();
        Deque<Integer> second = new ArrayDeque<>();

        for (ListNode node = l1; node != null; node = node.next) {
            first.push(node.val);
        }

        for (ListNode node = l2; node != null; node = node.next) {
            second.push(node.val);
        }

        ListNode head = null;
        int carry = 0;

        while (!first.isEmpty() || !second.isEmpty() || carry != 0) {
            int sum = carry;

            if (!first.isEmpty()) {
                sum += first.pop();
            }

            if (!second.isEmpty()) {
                sum += second.pop();
            }

            ListNode node = new ListNode(sum % 10);

            node.next = head;
            head = node;
            carry = sum / 10;
        }

        return head;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    first := make([]int, 0)
    second := make([]int, 0)
    for node := l1; node != nil; node = node.Next {
        first = append(first, node.Val)
    }
    for node := l2; node != nil; node = node.Next {
        second = append(second, node.Val)
    }

    var head *ListNode
    carry := 0
    for len(first) > 0 || len(second) > 0 || carry != 0 {
        sum := carry
        if len(first) > 0 {
            sum += first[len(first)-1]
            first = first[:len(first)-1]
        }
        if len(second) > 0 {
            sum += second[len(second)-1]
            second = second[:len(second)-1]
        }
        head = &ListNode{
            Val:  sum % 10,
            Next: head,
        }
        carry = sum / 10
    }
    return head
}

复杂度分析

时间复杂度：$O(m + n)$，两条链分别入栈一次、出栈一次，最多再处理一位最终进位。

空间复杂度：$O(m + n)$，用于两个数位栈；返回链表另外占 $O(\max(m,n))$ 空间。

关键点总结

[!green]

栈改变读取顺序，使正序链表也能从低位开始加法。

正序结果要用头插，逆序结果要用尾插，两种题型的加法与进位规则相同。

遍历输入只读取值，不反转或修改原链表。

易错点总结

[!yellow]

两种存储顺序不能混用：逆序从链头取低位并尾插，正序先借助栈取低位再头插。

循环条件用“与”会在短链或短栈耗尽时提前停止，应检查两边与进位是否任一仍有内容。

输入耗尽后仍可能存在最高位进位，不能提前结束。

本位取模十，进位整除十，两者必须基于同一个未修改的 sum。

基础解法返回 dummy.next；进阶解法返回实际结果头，避免输出占位节点。

相似题目

题目	难度	关联与区别
445. 两数相加 II	中等	加法规则相同，原题高位在链头，需栈或反转后才能先处理低位。
415. 字符串相加	简单	同样逐位求和与进位，字符串从末尾读取，本题链表已经按低位在前排列。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/25305190

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！