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

Question

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?

cdhowie · Accepted Answer · 2024-12-15 18:56:27Z

5

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();
        }
    }
}

4 Comments

Stochastic Sanity Dec 15, 2024 at 19:08

Thank you very much! For anyone else who finds this solution, you will immediately get errors from every previous problem about not implementing the copy trait. To fix these, you have to change all your instances of node.next to node.next.take() and make the variables mutable.

cdhowie Dec 15, 2024 at 19:12

@StochasticSanity That seems unrelated. It's also in code not in your question, because I didn't hit that when testing.

cdhowie Dec 15, 2024 at 19:15

@StochasticSanity Oh, I think it might be related after all, since you can't partially move from a type implementing Drop. But yeah, it's in other code not in your question.

Stochastic Sanity Dec 16, 2024 at 4:17

No, it's not, thats why I said "For anyone else who finds this solution" - because if they're in the same place I am, it'll be helpful for them. It's likely, since leetcode provides the singly linked list template code, and the rest is idiomatic.

Collectives™ on Stack Overflow

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

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related