Rust 实现链表两数相加算法详解

原题

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

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

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

迭代解法

代码

impl Solution {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail: &mut ListNode = &mut dummy;
        let mut p1 = l1;
        let mut p2 = l2;
        let mut carry = 0;

        while p1.is_some() || p2.is_some() || carry != 0 {
            let val1 = p1.as_ref().map_or(0, |node| node.val);
            let val2 = p2.as_ref().map_or(0, |node| node.val);
            let sum = val1 + val2 + carry;
            carry = sum / 10;
            tail.next = Some(Box::new(ListNode::new(sum % 10)));
            tail = tail.next.as_mut().unwrap();
            p1 = p1.and_then(|node| node.next);
            p2 = p2.and_then(|node| node.next);
        }
        dummy.next
    }
}

拆解分析

/// 主函数：两数相加（迭代版本） /// 【函数作用】入口函数，创建哑节点并启动迭代过程 /// 【参数所有权】l1, l2: 转移所有权（Option<Box> 被消耗） /// 【返回值】Option<Box>：新链表的所有权，不可变 pub fn add_two_numbers(...) {...}

// ======================================== // 哑节点（Dummy Node） // ======================================== // 【变量】dummy // 【类型】Box // 【所有权】dummy 拥有这个 Box 的所有权 // 【作用】占位节点，简化头节点处理，dummy.next 就是结果链表的头 let mut dummy = Box::new(ListNode::new(0));

// ======================================== // 尾指针（Tail Pointer） // ======================================== // 【变量】tail // 【类型】&mut ListNode（可变引用） // 【借用关系】tail 可变借用 dummy，指向当前链表的最后一个节点 // 【作用】用于在尾部追加新节点，避免遍历找尾 // 【生命周期】'dummy，不能比 dummy 活得长 let mut tail: &mut ListNode = &mut dummy;

// ======================================== // 遍历指针 // ======================================== // 【变量】p1, p2 // 【类型】Option<Box>，可变 // 【所有权】从 l1, l2 转移而来，p1 拥有 l1 链表的所有权，p2 同理 // 【作用】遍历两个输入链表，从不可变转换为可变 let mut p1 = l1; let mut p2 = l2;

// ======================================== // 进位 // ======================================== // 【变量】carry // 【类型】i32，可变 // 【所有权】Copy 类型，复制语义，无所有权转移问题 // 【作用】保存上一位的进位值（0 或 1） let mut carry = 0;

// ======================================== // 主循环 // ======================================== // 【循环条件】p1，p2 还存在节点未处理，或还有进位未处理 while p1.is_some() || p2.is_some() || carry != 0 {...}

// ----------------------------------------
// 获取当前位的值（安全地借用）
// ----------------------------------------
// 【方法】as_ref()
// 【作用】将 Option<Box<T>> 转为 Option<&Box<T>>，只借用不转移所有权
// 【变量】val1, val2
// 【类型】i32
// 【所有权】Copy 类型，直接复制值

    // ----------------------------------------
    // 【方法】map_or()
    // 【作用】将 node 的 val 拿出，无则默认 0
    let val1 = p1.as_ref().map_or(0, |node| node.val);
    let val2 = p2.as_ref().map_or(0, |node| node.val);

    // ----------------------------------------
    // 计算和与进位
    // ----------------------------------------
    let sum = val1 + val2 + carry;
    carry = sum / 10;  // 新的进位

    // ----------------------------------------
    // 创建新节点并追加到结果链表
    // ----------------------------------------
    // 【右侧】Box::new(ListNode::new(...)) 创建新 Box，拥有新节点的所有权
    // 【赋值】tail.next = Some(...)
    // 【所有权转移】新 Box 的所有权被转移进 tail.next 的 Option 中
    tail.next = Some(Box::new(ListNode::new(sum % 10)));//sum % 10 是进位后余下的数字

    // ----------------------------------------
    // 移动尾指针到新节点
    // ----------------------------------------
    // 【方法】as_mut().unwrap()
    // 【作用】as_mut() 将 Option<&Box<T>> 转为 Option<&mut Box<T>>
    //       unwrap() 取出 &mut Box<T>
    // 【关键】这里必须重新借用，因为 tail 是 &mut ListNode，
    //       我们需要获取 tail.next 的可变引用
    // 【所有权】tail 重新借用，指向新创建的节点
    tail = tail.next.as_mut().unwrap();

    // ----------------------------------------
    // 移动遍历指针到下一个节点（消耗所有权）
    // ----------------------------------------
    // 【方法】and_then(|node| node.next)
    // 【作用】消耗 p1 的 Option，取出 Box，返回 node.next
    // 【所有权转移】p1 原来的 Box 被消耗，p1 现在拥有下一个节点的所有权
    // 【注意】如果 p1 是 None，and_then 返回 None，p1 变为 None
    p1 = p1.and_then(|node| node.next);
    p2 = p2.and_then(|node| node.next);

// ========================================
// 返回结果
// ========================================
// 【返回值】dummy.next
// 【所有权转移】dummy.next 的 Option<Box<ListNode>> 所有权转移到函数返回值
// 【注意】dummy 本身在这里被 drop，但 dummy.next 已经被转移，所以没问题
dummy.next

过程

初始状态： l1 ──► Box ──► Box ──► None l2 ──► Box ──► None

执行后： l1, l2 被消耗（所有权转移到 p1, p2，然后逐步消耗）

dummy ──► Box │ ▼ next ──► Box ──► Box ──► Box ──► None ▲ tail ───────────────┘（可变引用，逐步后移）

返回值：dummy.next 的所有权被转移给调用者

递归解法

代码

impl Solution {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        Self::add_helper(l1, l2, 0)
    }

    fn add_helper(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
        carry: i32,
    ) -> Option<Box<ListNode>> {
        if l1.is_none() && l2.is_none() && carry == 0 {
            return None; // 返回 None，不创建新节点
        }
        let val1 = l1.as_ref().map_or(0, |node| node.val);
        let val2 = l2.as_ref().map_or(0, |node| node.val);
        let sum = val1 + val2 + carry;
        let new_carry = sum / 10;
        let mut node = Box::new(ListNode::new(sum % 10));
        let next1 = l1.and_then(|node| node.next);
        let next2 = l2.and_then(|node| node.next);
        node.next = Self::add_helper(next1, next2, new_carry);
        Some(node)
    }
}

拆解分析

/// 主函数：两数相加（递归版本入口） /// /// 【函数作用】提供简洁的 API，隐藏递归细节 /// 【参数所有权】l1, l2: 转移所有权 /// 【返回值】Option<Box>：新链表的所有权 pub fn add_two_numbers(...) {...}

// 调用辅助函数，初始进位为 0 Self::add_helper(l1, l2, 0)

/// 递归辅助函数 /// /// 【函数作用】递归处理每一位的相加 /// 【参数】 /// - l1: Option<Box> - 链表 1 的当前节点（拥有所有权） /// - l2: Option<Box> - 链表 2 的当前节点（拥有所有权） /// - carry: i32 - 进位值（Copy 类型） /// 【返回值】Option<Box> - 当前位及之后所有节点组成的新链表 fn add_helper(...) {...}

// ========================================
// 递归终止条件
// ========================================
// 【判断】两个链表都为空，且没有进位
// 【原因】没有需要处理的位了
if l1.is_none() && l2.is_none() && carry == 0 {
    return None;  // 返回 None，不创建新节点
}

// ========================================
// 获取当前位的值（借用检查）
// ========================================
// 【方法】as_ref()
// 【作用】安全地借用 l1 和 l2 内部的值，不转移所有权
// 【原因】我们需要 l1 和 l2 的所有权来获取它们的 next
// 【变量】val1, val2
// 【类型】i32（Copy，直接复制）
let val1 = l1.as_ref().map_or(0, |node| node.val);
let val2 = l2.as_ref().map_or(0, |node| node.val);

// ======================================== // 计算和与新的进位 // ======================================== let sum = val1 + val2 + carry; let new_carry = sum / 10;

// ========================================
// 创建当前结果节点
// ========================================
// 【变量】node
// 【类型】Box<ListNode>
// 【所有权】node 拥有这个新创建节点的所有权
let mut node = Box::new(ListNode::new(sum % 10));

// ========================================
// 准备递归参数（关键：所有权转移）
// ========================================
// 【方法】and_then(|node| node.next)
// 【作用】消耗 l1 的 Option，取出 Box，返回其中的 next 字段
// 【所有权转移】
//   - l1 的 Box<ListNode> 被 move 进闭包参数 node
//   - 闭包返回 node.next（Option<Box<ListNode>>）
//   - 这个 Option 成为 next1 的值
// 【结果】l1 被消耗，next1 拥有剩余链表的所有权
let next1 = l1.and_then(|node| node.next);
let next2 = l2.and_then(|node| node.next);

// ======================================== // 递归调用（所有权转移给递归函数） // ======================================== // 【赋值】node.next // 【右侧】Self::add_helper(next1, next2, new_carry) // 【所有权转移】 // - next1, next2 的所有权转移给递归函数 // - 递归函数返回 Option<Box>（剩余结果链表） // - 这个 Option 被赋值给 node.next node.next = Self::add_helper(next1, next2, new_carry);

// ======================================== // 返回当前节点 // ======================================== // 【返回值】Some(node) // 【所有权转移】node（Box）的所有权被封装进 Some，转移给调用者 Some(node)

过程

调用：add_two_numbers(l1, l2) │ ▼ add_helper(l1=Node(2)->Node(4)->Node(3), l2=Node(5)->Node(6)->Node(4), carry=0) │ ├── 计算：2+5+0=7，创建 Node(7) │ ├── 准备 next：l1.and_then(...) → Node(4)->Node(3) │ l2.and_then(...) → Node(6)->Node(4) │ └── 递归调用 ──────────────────────────────────────────────┐ │ │ add_helper(l1=Node(4)->Node(3), l2=Node(6)->Node(4), 0) │ │ │ ├── 计算：4+6+0=10，创建 Node(0)，new_carry=1 │ │ │ └── 递归调用 ──────────────────────────────────────┐ │ │ │ │ add_helper(l1=Node(3), l2=Node(4), carry=1) │ │ │ │ │ ├── 计算：3+4+1=8，创建 Node(8) │ │ │ │ │ └── 递归调用 ──────────────────────────────┐ │ │ │ │ │ │ add_helper(None, None, carry=0) │ │ │ │ │ │ │ └── 返回 None（终止条件）◄─────────────┘ │ │ │ │ node.next = None │ 返回 Some(Node(8)) ◄───────────────────────┘ │ node.next = Some(Node(8)) │ 返回 Some(Node(0)) ◄────────────────────────────┘ │ node.next = Some(Node(0)) │ 返回 Some(Node(7)) ◄────────────────────────────────────┘ │ 最终结果：7 -> 0 -> 8

对比

特性 迭代法 递归法
空间复杂度 O(1) 额外空间 O(n) 递归栈空间
代码长度 稍长 更简洁
Rust 难度 需要处理尾指针生命周期 所有权转移更直观
工业推荐 ✅ 推荐 教学/面试常用
尾递归优化 不适用 Rust 不保证优化

技巧

// 1. 只读访问，不转移所有权 let val = list.as_ref().map(|n| n.val);

// 2. 修改内容，不转移所有权 let val = list.as_mut().map(|n| n.val += 1);

// 3. 转移所有权，获取下一个节点 let next = list.and_then(|n| n.next);

// 4. 取出值，原变量变 None（常用于链表操作） let taken = list.take(); // list 变为 None

// 5. 可变引用重新赋值（迭代法关键） tail = tail.next.as_mut().unwrap();