LeetCode 面试题 02.05. 链表求和

Categories:

题目描述
思路分析
1. 解法一：模拟逐位相加（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 面试题 02.05. 链表求和

思路分析

解法一：模拟逐位相加（推荐）

核心思路：

两个链表按逆序存储数字，个位在链表头部，天然对齐，直接从头开始逐位相加。

维护进位变量 carry，每一位的结果为 (l1.val + l2.val + carry) % 10，新进位为 (l1.val + l2.val + carry) / 10。

同时遍历两个链表，某条链表遍历完后将其值视为 0，继续处理另一条链表及剩余进位。

循环终止条件：两个链表均为 null 且进位为 0；若最终 carry > 0，需额外创建一个值为 carry 的节点。

复杂度分析：

时间复杂度：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;
            }

            // 计算当前位结果与新进位
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }

        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 哑节点简化头节点处理
    dummy := &ListNode{}
    cur := dummy
    carry := 0

    // 只要还有节点未处理或存在进位，就继续循环
    for l1 != nil || l2 != nil || carry > 0 {
        sum := carry

        // 取 l1 当前位的值
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }

        // 取 l2 当前位的值
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        // 计算当前位结果与新进位
        carry = sum / 10
        cur.Next = &ListNode{Val: sum % 10}
        cur = cur.Next
    }

    return dummy.Next
}

解法二：递归

核心思路：

将逐位相加的过程用递归表达：每次计算两个节点之和加上进位，当前节点值为 sum % 10，进位 carry = sum / 10 传入下一层递归。

递归终止条件：两个节点均为 null 且进位为 0。

代码简洁，但递归深度为 max(m, n)，存在栈溢出风险，实际场景推荐迭代写法。

复杂度分析：

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

空间复杂度：O(max(m, n))，递归调用栈深度为 max(m, n) + 1。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1, l2, 0);
    }

    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        // 两个节点均为 null 且无进位时，递归终止
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }

        int sum = carry;

        // 取 l1 当前位的值
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }

        // 取 l2 当前位的值
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }

        // 当前节点值为 sum % 10，进位传入下层递归
        ListNode node = new ListNode(sum % 10);
        node.next = helper(l1, l2, sum / 10);
        return node;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return helper(l1, l2, 0)
}

func helper(l1, l2 *ListNode, carry int) *ListNode {
    // 两个节点均为 nil 且无进位时，递归终止
    if l1 == nil && l2 == nil && carry == 0 {
        return nil
    }

    sum := carry

    // 取 l1 当前位的值
    if l1 != nil {
        sum += l1.Val
        l1 = l1.Next
    }

    // 取 l2 当前位的值
    if l2 != nil {
        sum += l2.Val
        l2 = l2.Next
    }

    // 当前节点值为 sum % 10，进位传入下层递归
    node := &ListNode{Val: sum % 10}
    node.Next = helper(l1, l2, sum/10)
    return node
}

相似题目

题目	难度	考察点
2. 两数相加	中等	链表 / 进位处理
445. 两数相加 II	中等	链表 / 栈反转 + 进位
67. 二进制求和	简单	字符串 / 进位处理
415. 字符串相加	简单	字符串 / 进位处理
43. 字符串相乘	中等	字符串 / 逐位相乘
369. 给单链表加一	中等	链表 / 进位

本文作者: HGNULB

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