Rust中超长度链表测试栈溢出的原因排查与解决

问题背景 #

我在实现LeetCode第234题的is_palindrome函数时，加入了链表节点数校验逻辑，确保节点数在[1, 10^5]范围内：

impl Solution {
    pub fn is_palindrome(mut head: Option<Box<ListNode>>) -> bool {
        let mut list_length = 0;
        let mut length_counter = &head; 
        while let Some(node) = length_counter {
            length_counter = &node.next;
            list_length += 1;

            if list_length > 100_000 {
                panic!("The number of nodes in the list exceeds the maximum allowed length of 10^5");
            }
        }
        false // 占位逻辑
    }
}

为验证该校验逻辑，我编写了测试用例，传入包含100001个节点的链表：

#[cfg(test)]
mod constraints {
    use super::*;

    #[test]
    #[should_panic]
    /// 测试链表节点数超出最大限制的情况
    fn node_len_max() {
        let input = ListNode::from_vec(vec![5; 100_001]);
        let _output = Solution::is_palindrome(input);
    }
}

测试依赖的ListNode定义及转换方法如下：

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    // Vec转链表（仅测试用）
    pub fn from_vec(vec: Vec<i32>) -> Option<Box<ListNode>> {
        let mut iter = vec.into_iter().rev();
        let mut head = None;
        while let Some(val) = iter.next() {
            let node = Box::new(ListNode { val, next: head });
            head = Some(node);
        }
        head
    }
}

运行cargo test时触发栈溢出：

thread 'problems::mve::constraints::node_len_max' has overflowed its stack
fatal runtime error: stack overflow

我原本认为Vec和Box<ListNode>都在堆上分配，不会出现栈溢出，想明确两个问题：

1. 我做出了哪些错误假设？
2. 如何修复该测试使其正常运行？

1. 错误假设分析 #

• 错误假设1：链表销毁完全在堆上进行
  虽然Box<ListNode>是堆分配的，但Rust对嵌套Box的默认Drop实现是递归的：销毁一个Box<ListNode>时，会先递归销毁其next字段指向的Box<ListNode>，直到链表末尾。对于10万级别的链表，这种递归调用会直接耗尽栈空间，触发栈溢出。

• 错误假设2：测试过程中无栈消耗风险
  测试用例创建完长链表后，当测试函数退出时，链表会被自动销毁，此时递归Drop的调用栈深度等于链表长度，远超默认栈大小（通常几MB，对应数万级递归调用）。

2. 修复方案 #

方案一：手动实现迭代式Drop trait（推荐） #

给ListNode实现自定义Drop，用迭代方式销毁链表，避免递归栈溢出：

impl Drop for ListNode {
    fn drop(&mut self) {
        let mut current = self.next.take();
        // 迭代遍历销毁每个节点，避免递归
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

方案二：测试用例中手动控制链表销毁 #

用std::panic::catch_unwind捕获panic，之后手动迭代销毁链表，避免递归：

#[test]
#[should_panic]
fn node_len_max() {
    let input = ListNode::from_vec(vec![5; 100_001]);
    let result = std::panic::catch_unwind(|| {
        Solution::is_palindrome(input)
    });

    // 手动销毁链表（如果panic后还有剩余节点）
    if let Ok(mut head) = result.err().and_then(|p| p.downcast::<Option<Box<ListNode>>>()) {
        while let Some(mut node) = head.take() {
            head = node.next.take();
        }
    }

    assert!(result.is_err());
}

方案三：优化校验逻辑，提前截断链表 #

在is_palindrome的校验逻辑中，触发panic前手动截断链表，减少后续销毁时的递归深度：

pub fn is_palindrome(mut head: Option<Box<ListNode>>) -> bool {
    let mut list_length = 0;
    let mut length_counter = &mut head; 
    while let Some(node) = length_counter {
        list_length += 1;

        if list_length > 100_000 {
            // 截断链表，避免后续递归销毁栈溢出
            node.next.take();
            panic!("The number of nodes in the list exceeds the maximum allowed length of 10^5");
        }
        length_counter = &mut node.next;
    }
    false
}

内容的提问来源于stack exchange，提问作者Stochastic Sanity