In rust, How to allocate a large vector to a linked list without stack overflow?

I am doing problem 234 from LeetCode. I have a function which takes as its input a linked list:

impl Solution {
    pub fn is_palindrome(mut head: Option<Box<ListNode>>) -> bool {

And has a check to ensure that the list is in the range [1, 10e5]

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

as per the constraints of the problem.

I have the following test:

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

    #[test]
    #[should_panic]
    /// The number of nodes in the list is in the range `[1, 10e5]`.
    fn node_len_max() {
        let input = ListNode::from_vec(vec![5; 100_001]);
    let _output = Solution::is_palindrome(input);
    }
}

That relies on the following struct and impl:

/// Definition for singly-linked list.
#[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 }
    }

    // Convert from Vec<i32> to ListNode
    // Only used for tests since LeetCode defines ListNode
     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
    }
}

When running the code with cargo test, I get:

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

Here is a minimum viable example:

#[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 }
    }

    // Convert from Vec<i32> to ListNode
    // Only used for tests since LeetCode defines ListNode
     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
    }
}

pub struct Solution;
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 // Place holder for mve 
    }
}



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

    #[test]
    #[should_panic]
    /// The number of nodes in the list is in the range `[1, 10e5]`.
    fn node_len_max() {
        let input = ListNode::from_vec(vec![5; 100_001]);
    let _output = Solution::is_palindrome(input);
    }
}

I am confused here, as I assumed that operations were being performed on the heap, as a vector would be allocated on the heap, and the ListNode is boxed.

What assumptions am I making incorrectly here?
How can I fix this test to run?

Solution

The default Drop implementation for ListNode is going to be recursive. This means over 100k stack frames are required to clean up this linked list. The stack overflow is therefore occurring when dropping the list, not when building it.

You need to write your own Drop implementation that iteratively drops the list instead.

For example:

impl Drop for ListNode {
    fn drop(&mut self) {
        let mut node = self.next.take();

        while let Some(mut i) = node {
            node = i.next.take();
        }
    }
}