leetcode 链表 两数相加 rust解法分析

Ne0inhk

— 14 min read

原题

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

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

你可以假设除了数字 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<ListNode>> 被消耗）
    /// 【返回值】Option<Box<ListNode>>：新链表的所有权，不可变
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {...}
        // ========================================
        // 哑节点（Dummy Node）
        // ========================================
        // 【变量】dummy
        // 【类型】Box<ListNode>
        // 【所有权】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<ListNode>>，可变
        // 【所有权】从 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<Node1> ──► Box<Node2> ──► None
l2 ──► Box<Node3> ──► None

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

dummy ──► Box<Dummy> 
            │
            ▼
         next ──► Box<Result1> ──► Box<Result2> ──► Box<Result3> ──► 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<ListNode>>：新链表的所有权
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {...}
// 调用辅助函数，初始进位为 0
        Self::add_helper(l1, l2, 0)
     /// 递归辅助函数
    /// 
    /// 【函数作用】递归处理每一位的相加
    /// 【参数】
    ///   - l1: Option<Box<ListNode>> - 链表1的当前节点（拥有所有权）
    ///   - l2: Option<Box<ListNode>> - 链表2的当前节点（拥有所有权）
    ///   - carry: i32 - 进位值（Copy 类型）
    /// 【返回值】Option<Box<ListNode>> - 当前位及之后所有节点组成的新链表
    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，不创建新节点
        }
        // ========================================
        // 获取当前位的值（借用检查）
        // ========================================
        // 【方法】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<ListNode>>（剩余结果链表）
        //   - 这个 Option 被赋值给 node.next
        node.next = Self::add_helper(next1, next2, new_carry);
 // ========================================
        // 返回当前节点
        // ========================================
        // 【返回值】Some(node)
        // 【所有权转移】node（Box<ListNode>）的所有权被封装进 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();
 

Read more

OpenClaw dashboard命令后，无法登录web控制面板（在systemd服务无法启动的一些虚拟机里会碰到）

OpenClaw dashboard命令后，无法登录web控制面板（在systemd服务无法启动的一些虚拟机里会碰到）

先上结论 执行OpenClaw dashboard命令后，无法登录web控制面板，是因为OpenClaw的gateway服务没有起来。原来小龙虾OpenClaw 的命令没有学明白，先弄清楚命令： openclaw onboard 是配置 openclaw dashboard是显示web控制面板登录信息 openclaw gateway --verbose 是启动网关 openclaw gateway start是启动网关服务 问题就是因为这台系统的systemd没有起作用，导致openclaw的gateway服务没有起来，所以控制面板无法登录。 OpenClaw status Overview ┌─────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────┐ │ Item │ Value │ ├─────────────────┼────────────────────────────────────

By Ne0inhk

【前端高级特效】使用 CSS 实现毛玻璃模糊背景效果

使用 CSS 实现毛玻璃（Frosted Glass / 毛玻璃 / 磨砂玻璃）模糊背景效果 这是 2024–2026 年非常流行的前端高级视觉效果之一，常用于： * 模态框 / 抽屉 / 侧边栏的背景 * 卡片悬浮在模糊背景上 * 导航栏 / 工具栏的半透明磨砂感 * 音乐播放器、天气小组件、桌面壁纸风格 UI 当前最主流的实现方式对比（2025–2026） 方案核心属性浏览器支持（2025）性能真实感推荐指数备注1backdrop-filter: blur()极好（几乎全覆盖）中～高★★★★★★★★★★首选2filter: blur() + 伪元素完美支持中★★★☆☆★★☆☆☆老项目兼容用3SVG 滤镜 + feGaussianBlur完美支持较低★★★★☆★☆☆☆☆极致兼容用4canvas / WebGL 实时模糊完美支持较低～中★★★★★★★☆☆☆动态内容才考虑 结论：99% 的现代项目直接使用 backdrop-filter: blur(

By Ne0inhk
【优选算法篇】编织算法的流动诗篇：滑动窗口的轻盈之美

【优选算法篇】编织算法的流动诗篇：滑动窗口的轻盈之美

文章目录 * C++ 滑动窗口详解：基础题解与思维分析 * 前言 * 第一章：热身练习 * 1.1 长度最小的子数组 * 解法一（暴力求解） * 解法二（滑动窗口） * 滑动窗口的核心思想 * 图解分析 * 滑动窗口的有效性 * 时间复杂度分析 * 易错点提示 * 1.2 无重复字符的最长子串 * 解法一（暴力求解） * 解法二（滑动窗口） * 图解分析 * 详细说明： * 1.3 最大连续 1 的个数 III * 解法（滑动窗口） * 滑动窗口的核心思想 * 图解分析 * 详细说明： * 关键点： * 1.4 将 x 减到 0 的最小操作数 * 解法（滑动窗口）： * 算法流程：

By Ne0inhk
【数据结构】哈希扩展学习

【数据结构】哈希扩展学习

目录 1. 位图 1.1 位图相关面试题 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的一个面试题） 1.2 位图的设计及实现 1.3 C++库中的位图 bitset 1.4 位图的优缺点 1.5 位图相关考察题目 • 给定100亿个整数，设计算法找到只出现一次的整数？ • 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？ • 一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数 2. 布隆过滤器 2.1 什么是布隆过滤器 2.2 布隆过滤器器误判率推导 2.3 布隆过滤器代码实现 2.4 布隆过滤器删除问题 2.

By Ne0inhk