2
\$\begingroup\$

Yesterday, inspired by some great questions here, I decided to give myself some practice with Rust, by solving all the introductory questions over on LeetCode. It was a great learning exercise, and one of the problems left me wanting your advice: “Middle of the Linked List”

Their summary of the problem:

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

The Code

pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
  fn iterate_unevenly( a: &Option<Box<ListNode>>,
                       b: &Option<Box<ListNode>>
                     ) -> Option<Box<ListNode>> {
    if let Some(next) = b {
      if let Some(nextnext) = &next.next {
        if let Some(slow) = a {
          iterate_unevenly( &slow.next, &nextnext.next )
        } else { // Can’t happen.
          a.clone() // cloning the list to work around Rust's borrow checker is not ideal.
        }
      } else {
        a.clone()
      }
    } else {
      a.clone()
    }
  }

  return iterate_unevenly(&head, &head) // The head should be moved, if possible.
}

In order to compile this at home, you will also need the following boilerplate from LeetCode. For this exercise, I needed to work with their API, and could not change any of this or the type of middle_node (although I suppose I might have added traits to ListNode).

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

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

I also wrote a simple test driver. I’m happy to get feedback on it, too, even though it’s not my main focus.

fn show(head: &Option<Box<ListNode>>) -> String {
  let mut current : &Option<Box<ListNode>> = head;
  let mut result = String::from("[");

  if let Some(node) = current {
    result += &node.val.to_string();
    current = &node.next;
  }

  while let Some(node) = current {
     result += ", ";
     result += &node.val.to_string();
     current = &node.next;
  }

  result.push(']');
  return result
}


fn list_from_slice(xs: &[i32]) -> Option<Box<ListNode>> {
  fn helper( ys: &[i32],
             inner: Option<Box<ListNode>>
           ) -> Option<Box<ListNode>> {
    if ys.is_empty() {
      inner
    } else {
      let omega = ys.len()-1;

      helper( &ys[..omega],
              Some(Box::new(ListNode{
               val: ys[omega],
               next: inner
              }))
            )
    }
  }

  return helper( xs, None )
}


pub fn main()
{
    let test_data : Option<Box<ListNode>> =
      list_from_slice(&[1,2,3,4,5]);

    println!("{}", show(&test_data));

    println!("{}", show(&middle_node(test_data)) );
}

Some Things I’d Like Advice on

The reason I’m asking about this problem is what bothered me enough to leave comments. The code was fast enough to get a 0 ms time, but what I ended up having to do to satisfy the borrow checker was to clone the entire back half of the list. (I believe this makes a deep copy of every trailing node, although I’m not absolutely certain.) This is wasteful. What I really wanted to do was have the first parameter of iterate_unevenly own the list, and the second be an iterator that weakly aliases it. In this context, the references are used safely, because the second iterator is always ahead of or in a tie with the first, referencing a node that has not been discarded yet, but Rust only sees that I’m trying to borrow a moved object. Failing that, I would want to move the middle node of the list to the return value, or swap them.

Of course, I could solve the problem in another way (such as by making one pass with a borrowed iterator to count the nodes and then passing ownership to a function that drops the first half of them). Or, if I could change the API to borrow rather than consume a linked list, this issue would go away. But I’d like to better understand how to make the algorithm I used work in the Rust type system.

I think it’s pretty obvious that I do a lot of functional programming, I format manually, and I’m still figuring out the idioms. If something about my style is distracting or confusing, please let me know.

In particular, the iterate_unevenly helper function is a Pyramid of Doom. There’s something reassuring about writing out every branch and having the compiler double-check that each one produces a single value of the correct type, but three of the four are duplicated. I could save a half-dozen lines just by making the innermost branch a return statement and adding another return after the nested if as a fall-through, like I would in C. But is there a better way? Haskell, for example, has some nice syntactic sugar to flatten computations on an option type so they’ll return either a result or Nothing.

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$
    } else { // Can’t happen.
      a.clone() // cloning the list to work around Rust's borrow checker is not ideal.
    }

Please don't ever do this. If a certain situation should never happen the worse possible thing you do is silently do something that will probably be wrong if it somehow happens. Rust has an unreachable!() macro you can use for this which will panic if the code somehow reaches a state that shouldn't be reachable. Alternately, use unwrap or expect on the option.

The code was fast enough to get a 0 ms time, but what I ended up having to do to satisfy the borrow checker was to clone the entire back half of the list. (I believe this makes a deep copy of every trailing node, although I’m not absolutely certain.)

Firstly, you are correct, this makes a deep copy of every trailing node.

This issue was discussed on Stackoverflow, with the conclusion that you can't avoid the clone with the interface dictated by LeetCode. Basically, its beyond the borrow checker to track what you are doing here.

But is there a better way? Haskell, for example, has some nice syntactic sugar to flatten computations on an option type so they’ll return either a result or Nothing.

Rust's Option type has methods that let you do these kinds of operations, so you can do something like:

 fn iterate_unevenly(
        a: Option<Box<ListNode>>,
        b: &Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        b.as_ref()
            .and_then(|next| next.next.as_ref())
            .map(|nextnext| iterate_unevenly(a.unwrap().next, &nextnext.next))
            .unwrap_or_else(|| a.clone())
    }

Is it actually better than what you had? That's debateable.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks! a panic might be better in the first code sample. That particular condition is when the fast iterator’s next reference is valid, but the slow iterator is not, even though the fast iterator must have traversed past the slow iterator already, so there is some kind of logic error in the program if that branch is ever reached. \$\endgroup\$
    – Davislor
    Commented Oct 23, 2022 at 5:32
  • \$\begingroup\$ Maybe change if let Some(slow) = a; to let slow = a.unwrap();. Makes the code a little simpler too. There’s probably no runtime error message that’s more useful than the line of source. (No state to share: the bug is that the slow reference is empty.) \$\endgroup\$
    – Davislor
    Commented Oct 23, 2022 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.