I an using unsafe code to implement the LeetCode #234.
The input data is like this:
Some(Box(1)) -> Some(Box(2)) -> Some(Box(2)) -> Some(Box(1)) -> None
The first step is to revert the second half of the list. Make it to be:
Some(Box(1)) -> Some(Box(2)) -> Some(Box(1)) -> Some(Box(2)) -> None
The code snippet to doing so is as below (The full code is attached at the end):
let mut cur: *mut _ = p2; // p2 is the start of the second half of the whole list. Which is the 3rd node.
let mut prev: *mut Option<Box<ListNode>> = &mut None;
while (*cur).is_some() {
let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // PROBLEM LINE
println!("next: {:?}", *next); // next is None in second loop.
println!("cur: {:?}", *cur); // cur become None in second loop.
(*cur).as_mut().unwrap().next = (*prev).take(); // ERROR HAPPENS HERE
prev = cur;
cur = next;
}
The first loop works fine.
After first loop the cur is: Some(Box(1)) -> None
The prev is: Some(Box(2)) -> None
My expectation for 2nd loop is as below:
- Set
nextpointer tocur's next, which isNone. - Set
cur'snextto beprev. This can makecurto be:Some(Box(1)) -> Some(Box(2)) -> None - Set
prevpointer tocur. This doesn't matter. - Set
curpointer tonext. This doesn't matter.
The error happens on the 2nd step. The error is:
'called `Option::unwrap()` on a `None` value'
That means cur becomes None after the 1st step code which is:
let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // PROBLEM LINE
The take() is for the cur's next node, which is None. It should return a None, and leave the cur's next as None as well. It should not impact the value of cur.
I also tried to change the 1st step code to be:
let next: *mut _ = if (*cur).as_mut().unwrap().next.is_some() {
&mut (*cur).as_mut().unwrap().next.take()
} else {
&mut None
};
Then it works fine. But I think this alternative code should have same effect as the old 1st step code.
I tried to repro it with a small piece of code without loop, just do the same operations in sequence. It works without any problem. It can be executed on https://play.rust-lang.org/ directly.:
#![allow(unused)]
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
fn main() {
// make a list as 1 -> 2 -> 3 -> 4 -> None
let mut list = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 3, next: Some(Box::new(ListNode { val: 4, next: None })) })) })) }));
unsafe {
// let the pointer point to the 3rd node which has value 3.
let mut p: *mut _ = &mut list.as_mut().unwrap().next.as_mut().unwrap().next;
println!("p: {:?}", *p);
let mut cur: *mut _ = p;
let mut prev: *mut Option<Box<ListNode>> = &mut None;
// first loop
let mut next: *mut _ = &mut (*cur).as_mut().unwrap().next.take();
(*cur).as_mut().unwrap().next = (*prev).take();
prev = cur;
cur = next;
// second loop
mut next: *mut _ = &mut (*cur).as_mut().unwrap().next.take(); // The same of the problem code.
println!("next: {:?}", *next);
println!("cur: {:?}", *cur);
(*cur).as_mut().unwrap().next = (*prev).take();
prev = cur;
cur = next;
println!("list: {:?}", list);
println!("prev: {:?}", *prev);
}
}
The full code is attached as below. It can be executed on https://play.rust-lang.org/ directly.
#![allow(unused)]
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
if head.is_none() || head.as_ref().unwrap().next.is_none() {
return true;
}
unsafe {
let mut head = head;
let mut fast: *mut _ = &mut head;
let mut slow: *mut _ = &mut head;
while (*fast).as_ref().unwrap().next.is_some() && (*fast).as_ref().unwrap().next.as_ref().unwrap().next.is_some() {
slow = &mut (*fast).as_mut().unwrap().next;
fast = &mut (*fast).as_mut().unwrap().next.as_mut().unwrap().next;
}
let mut p1: *mut _ = &mut head;
let mut p2: *mut _ = &mut (*slow).as_mut().unwrap().next;
println!("p1: {:?}", *p1);
println!("p2: {:?}", *p2);
let mut cur: *mut _ = p2;
let mut prev: *mut Option<Box<ListNode>> = &mut None;
while (*cur).is_some() {
println!("new loop for cur: {:?}", *cur);
println!("cur: {:?}", *cur);
println!("prev: {:?}", *prev);
let next: *mut _ = &mut (*cur).as_mut().unwrap().next.take();
println!("next: {:?}", *next);
(*cur).as_mut().unwrap().next = (*prev).take();
println!("cur: {:?}", *cur);
prev = cur;
println!("prev: {:?}", *prev);
cur = next;
println!("cur: {:?}", *cur);
}
p2 = prev;
println!("p1: {:?}", *p1);
println!("p2: {:?}", *p2);
while (*p2).is_some() {
if (*p1).as_ref().unwrap().val != (*p2).as_ref().unwrap().val {
return false;
}
else {
p1 = &mut (*p1).as_mut().unwrap().next;
p2 = &mut (*p2).as_mut().unwrap().next;
}
}
return true;
}
}
fn main() {
let mut list = Some(Box::new(ListNode { val: 1, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 1, next: None })) })) })) }));
let result = is_palindrome(list);
println!("result: {:?}", result);
}
That's the first rule (of the fightclub 
). And if you do, don't use a block of around ~50 lines. That totally defeats the purpose of using Rust in the first place.
