My first solved problem with lists

Yeah, Rust is brutal when you have lists.

The problem: you get a list, return second half of it. I decided to solve it without using Clone.

Just for reference, this is canonical solution with Clone:

    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut fast = &head;
        let mut slow = &head;
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
            slow = &slow.as_ref().unwrap().next;
        }
        slow.clone()
    }

You traverse list in parallel, doing one step for ‘slow’ and two steps for ‘fast’. As soon as you got to the end of ‘fast’, you are in the middle of the slow. Return it.

For normal programming languages, returning here a pointer to ‘slow’ is not a problem. But not for Rust. You got ownership of the list, and you need return the owned list, by value. That means, that if you traverse by value, you deconstructing it (can not return), and if you traverse it by reference, you can’t return value (because you have only reference). So, people solve it by ‘Clone’. Which is, actually, additional allocation, and additional traversal.

There is second solution for the same problem: you traverse list once (by reference), record depth, and traverse list second time, by value, and stop when you are at half-depth, returning the current list head.

Which is okay…, but imagine, we have a veeeery long list, where second traversal adds a significant overhead. Can you do better?

I believe, I found the solution. My idea is to use recursion to get to the end of the list, remember the depth, and return depth with ‘head’. If current depth is half of total depth, we got to the solution and return it with a marker that ‘this is solution’.

I’ve just realized, that returning to the beginning of the list will take exactly the same time as a double traverse, so .. meh..,

Well, actually, my point here was not a solution I found, but a trick I want to show:

type BoxList = Option<Box<ListNode>>;

impl Solution {
    pub fn dive(head: BoxList, curr_depth: usize) -> (BoxList, Option<usize>) {
        match head {
            None => (head, Some(curr_depth)),
            Some(mut node) => {
                let (next, tail_depth) = 
                  Solution::dive(node.next, curr_depth + 1);
                match tail_depth {
                    Some(tail_depth) if tail_depth / 2 == curr_depth => {
                        node.next = next;
                        (Some(node), None)
                    }
                    Some(tail_depth) => {
                        node.next = next;
                        (Some(node), Some(tail_depth))
                    }
                    None => (next, None),
                }
            }
        }
    }

    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        Solution::dive(head, 0).0
    }
}

We traverse list by value, and when we reach end, we return depth (of length of the list).

When our ‘traverse’ function get back from recursion (when we traverse up), we do checks. The main neat thing here is this (simplified code):

let next = dive(node.next);
node.next = next;
return next;

Basically, we partially deconstruct node structure, consuming .next from it. Then we construct it back! Basically, I invented our own “borrow” system. I give function a value to use, and then place it back.

The list problem

The second thing I want to say is why I considered this problem (this class of problem) hard, is that I’ve tried to work with list via methods for ListNode structure. It’s wrong! All methods should work with Option<Box<ListNode>> type! And it’s trickier that you think, because you can’t impl Option<Box<ListNode>>.

The trick I found here is to create own trait List and do impl List for Option<Box<ListNode>>. This allow me to use self .