Hi There,
For this challenge Loading..., it's very easy to be done with C++, can some one gives me an example for how to do the same thing in Rust?
Sure, I can give an example. I’d have to say that the setup feels somewhat unidiomatic for Rust in terms of that impl Solution block as well as the fact that we’re working with an owned list instead of a mutable reference to the list. In any case, the owned list makes things even easier, perhaps. Also I have no idea whatsoever what they mean by that “You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)” statement. In any case… a simple recursive solution as follows would work:
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match head {
Some(mut node1) => {
match node1.next {
Some(mut node2) => {
std::mem::swap(&mut node1.val, &mut node2.val);
node2.next = Solution::swap_pairs(node2.next);
node1.next = Some(node2);
}
None => (),
}
Some(node1)
}
None => None,
}
}
}
(which basically exactly does “modifying the values in the list’s nodes”)
I guess it would indeed also be possible to re-link the nodes instead, modifying the relevant next fields. This code demonstrates how you can move out of fields of a value in a Box, (by which the value becomes “partially moved-out of”, in other words: it’s important that e.g. the node1.next field is moved back in in the end of that Some(mut node2) case above in order for the code to function.
It’s probably also possible to make this work with mutable references and a loop somehow instead of recursion.
Maybe using Option::take()?
Here’s a solution like that, but it’s still swapping the values, not re-connecting the nodes. Honestly, it wouldn’t make much sense at all though in Rust to actually re-connect the nodes here. In any case…
impl Solution {
pub fn swap_pairs(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut r = &mut head;
loop {
match r {
None => break,
Some(node1) => {
match &mut node1.next {
None => break,
Some(node2) => {
std::mem::swap(&mut node1.val, &mut node2.val);
r = &mut node2.next;
}
}
}
}
}
head
}
}
as the challenge asks, values cannot be swapped, so what I am looking for is the solution for swapping the "next", but yes, thanks for the example
I see, so does not make sense to reconnect the nodes in Rust, that's good one though, it's very suffering to do reconnect through my little knowledge
I found link lists are very subtle in Rust, is there any good references other than Layout - Learning Rust With Entirely Too Many Linked Lists this?
1 Like
Here’s a solution that updates only the .next pointers:
impl Solution {
pub fn swap_pairs(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut current = &mut head;
loop {
match current {
None => break,
Some(current_node) => {
match current_node.next.take() {
None => break,
Some(mut next_node) => {
// rewire stuff
current_node.next = next_node.next.take();
next_node.next = current.take();
*current = Some(next_node);
// advance two steps
current = &mut current.as_mut().unwrap().next.as_mut().unwrap().next;
}
}
}
}
}
head
}
}
1 Like
And finally, some more idiomatic solution: In Rust, we’d have an Iterator over that linked list type. Since we don’t have one in that example, we’ll need to build it ourselves, but that isn’t too hard:
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut list = LinkedList(head);
let mut iter = list.iter_mut();
while let (Some(val1), Some(val2)) = (iter.next(), iter.next()) {
std::mem::swap(val1, val2);
}
list.0
}
}
struct LinkedList(Option<Box<ListNode>>);
impl LinkedList {
fn iter_mut(&mut self) -> IterMut<'_> {
self.into_iter()
}
}
impl<'a> IntoIterator for &'a mut LinkedList {
type Item = &'a mut i32;
type IntoIter = IterMut<'a>;
fn into_iter(self) -> Self::IntoIter {
IterMut(self.0.as_deref_mut())
}
}
struct IterMut<'a>(Option<&'a mut ListNode>);
impl<'a> Iterator for IterMut<'a> {
type Item = &'a mut i32;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node| {
self.0 = node.next.as_deref_mut();
&mut node.val
})
}
}
(this on is, obviously, also a value-swapping solution)
Heh, here’s a fun idea: Make an iterator that returns Box<ListNode> (with .next fields being None), then re-connect the nodes as required.
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let list = LinkedList(head);
let mut nodes = list.nodes();
let mut result = None;
let mut previous_ptr = &mut result;
loop {
match (nodes.next(), nodes.next()) {
(Some(node1), Some(mut node2)) => {
// wire up two nodes in reverse order
node2.next = Some(node1);
*previous_ptr = Some(node2);
// borrow our way back into `node2` to get the next `previous_ptr`
previous_ptr = &mut previous_ptr.as_deref_mut().unwrap().next.as_deref_mut().unwrap().next;
}
(Some(node), None) => {
*previous_ptr = Some(node);
}
(None, _) => break
}
}
result
}
}
struct LinkedList(Option<Box<ListNode>>);
impl LinkedList {
/// Iterator that splits up the list into nodes
/// and returns them. (All the `.next` fields are `None`.)
fn nodes(self) -> Nodes {
Nodes(self.0)
}
}
struct Nodes(Option<Box<ListNode>>);
impl Iterator for Nodes {
type Item = Box<ListNode>;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|mut node| {
self.0 = node.next.take();
node
})
}
}
yeah, I figure it’s basically the same as what I did above with extra step, but I like it xD
One could take this further and create a general fn connect_nodes(i: impl Iterator<Item = Box<ListNode>>) -> LinkedList function (expecting an iterator of disconnected nodes). Then write an iterator adapter that swaps pairs of items in the iterator, and connect everything up with connect_nodes(list.nodes().swap_pairs()).
it looks like leetcode does not like the solution for the following code generates more pointer retrievals
current = &mut current.as_mut().unwrap().next.as_mut().unwrap().next;
@steffahn do you know any other solution that could be better than this? being frustrated with Rust without unsafe
impl Solution {
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if let Some(head_node) = head {
let mut new_head = Some(head_node);
let mut current: *mut _ = &mut new_head;
while let Some(ref mut current_node) = unsafe{&mut (*current)} {
if let Some(mut next_node) = current_node.next.take() {
current_node.next = next_node.next.take();
let next: *mut _ = &mut current_node.next;
next_node.next = unsafe{(*current).take()};
unsafe {*current = Some(next_node);}
current = next;
} else {
break
}
}
return new_head;
}
None
}
}
You've got to be careful when mixing use of mutable references and raw pointers like this in Rust. I'm not 100% sure, but it's not unlikely that this code could be considered to trigger UB, in particular I'm suspecting that the assignment *current = ... could be invalidating the pointer next, which was (with a few extra steps) derived from a mutable reference derived from current. But I'm not sure if there really is a problem or not, especially since the extra steps involved dereferencing a Box.
The main difficulty here is that we're working with the Box type for our next pointers. If the data structure itself used raw pointers instead, it would be easier to make a “for-sure”-UB-free implementation similar to yours above, because one could probably start writing almost fully C-style code.
In general, I'd avoid unsafe code if it isn't necessary. I. e. if there's a decent safe alternative. Re-dereferencing your way back through 2 layers of nodes might seem unnecessary but honestly the overhead is limited, and I wouldn't be surprised if compiler optimizations could help out even further - even if not, things will be at least still in cache.... heck, what are we even taking about: linked lists aren't very performant to begin with, no need to hand-optimize them with (potentially problematic) unsafe code in the first place.
I don't like unsafe neither.
here is what I can do with my best and least unsafe, again, I don't know how to get rid of the borrowing checking here to avoid unsafe. the double next following, I still don't think it's trivial, for example, in Loading... this case, you have to have a inner loop
pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
if let Some(head_node) = head {
let mut new_head = Some(head_node);
let mut current = &mut new_head;
while let Some(ref mut current_node) = current {
if let Some(mut next_node) = current_node.next.take() {
current_node.next = next_node.next.take();
let next: *mut _ = &mut current_node.next;
next_node.next = current.take();
*current = Some(next_node);
current = unsafe{&mut *next};
} else {
break
}
}
return new_head;
}
None
}
Basically don't use Leetcode. Their Rust exercises were translated poorly from some other language without any regard for what would be idiomatic or even implementable in Rust. The result is that you end up being more confused by the weird artificial limitations they put on you than by the language itself. Further detail here. Unfortunately nobody appears to maintain these exercises; I guess Leetcode is more interested in appearing to have a bunch of languages than in making any of them good.
5 Likes
Thanks for the info, yes, that's also my sense, I just want to have a place to practice Rust more before I decided to apply Rust for a real project, I want to get used to it and see what are the tricky stuff in Rust I could met in a real project. Do you have any suggestion for practicing Rust about the language and framework features in depth?
For example, in this case, I learned about take() to avoid let some introduces borrowings. also, the some other examples make me aware of std::mem::replace etc.
There are suggestions in that same link. (I was going to TL;DR the TL;DR, but upon reflection decided it's better if you just read the TL;DR so you see the non-practice-site suggestions as well.)
1 Like
Thanks for this!
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.