use std::cell::RefCell;
use std::cell::Ref;
use std::rc::Rc;
//707. 设计链表(LinkedList Design)
struct MyLinkedList {
length: i32,
head: Option<Rc<RefCell<LinkNode>>>,
tail: Option<Rc<RefCell<LinkNode>>>,
}
#[derive(Clone)]
struct LinkNode {
val: i32,
next: Option<Rc<RefCell<LinkNode>>>
}
impl LinkNode {
fn new(val:i32) -> Self {
LinkNode {
val,
next: None,
}
}
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyLinkedList {
/** Initialize your data structure here. */
fn new() -> Self {
MyLinkedList{
length: 0_i32,
head: None,
tail: None,
}
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
fn get(&self, index: i32) -> i32 {
if self.length <= index {
return -1;
}
let mut i = 0;
//let mut head = Rc::clone(&self.head.as_ref().unwrap());
let mut head = &self.head;
//let mut borrow_cur:Ref<LinkNode>;
while let Some(t) = head {
//let node = t.borrow();
if i == index {
unsafe {
return (*t.as_ptr()).val;
}
}
i += 1;
//head = & node.next;
unsafe {
head = & (*t.as_ptr()).next;
}
}
-1
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
fn add_at_head(&mut self, val: i32) {
if self.length == 0 {
let node = Rc::new(RefCell::new(LinkNode::new(val)));
self.head = Some(Rc::clone(&node));
self.tail = Some(Rc::clone(&node));
self.length += 1;
return
}
let head = self.head.take();
let mut node = LinkNode::new(val);
node.next = head;
self.head = Some(Rc::new(RefCell::new(node)));
self.length += 1;
return
}
/** Append a node of value val to the last element of the linked list. */
fn add_at_tail(&mut self, val: i32) {
let node = Rc::new(RefCell::new(LinkNode::new(val)));
if self.length == 0 {
self.head = Some(Rc::clone(&node));
self.tail = Some(Rc::clone(&node));
self.length += 1;
return
}
let tail = self.tail.take();
//let node = Rc::new(RefCell::new(LinkNode::new(val)));
if let Some(cur) = tail {
(*cur).borrow_mut().next = Some(Rc::clone(&node));
self.tail = Some(Rc::clone(&node));
self.length += 1;
}
return
}
fn debug_link_list(&self) -> Vec<i32> {
let mut head = &self.head;
let mut res = vec![];
while let Some(t) = head {
//eprintln!("{}",t.borrow().val);
res.push(t.borrow().val);
unsafe{
head = & (*(t.as_ptr())).next;
}
}
res
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
fn add_at_index(&mut self, index: i32, val: i32) {
if index > self.length || index < 0 {
return
}
if index == 0 {
self.add_at_head(val);
return
}
if index == self.length {
self.add_at_tail(val);
return
}
let mut i = 0;
let mut head = &(self.head);
while let Some(t) = head {
if i + 1 == index {
let mut prev = t.borrow_mut();
let next = prev.next.take();
let mut node = LinkNode::new(val);
node.next = next;
prev.next = Some(Rc::new(RefCell::new(node)));
self.length += 1;
return
}
i += 1;
unsafe {
head = & (*(t.as_ptr())).next;
}
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
fn delete_at_index(&mut self, index: i32) {
if index >= self.length || index < 0{
return
}
if index == 0 {
//let mut head = head;
let head = self.head.take();
if let Some(t) = head {
self.head = (*t).borrow_mut().next.take();
if self.length == 1 {
self.tail = None;
}
self.length -= 1;
return
}
return
}
let mut i = 0;
let mut head = &(self.head);
while let Some(t) = head {
if i + 1 == index {
let mut prev = t.borrow_mut();
let next = prev.next.take();
let next_next = (*(next.unwrap())).borrow_mut().next.take();
prev.next = next_next;
if self.length -1 == index {
self.tail = Some(Rc::clone(t));
}
self.length -= 1;
return
}
i += 1;
unsafe {
head = & (*(t.as_ptr())).next;
}
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* let obj = MyLinkedList::new();
* let ret_1: i32 = obj.get(index);
* obj.add_at_head(val);
* obj.add_at_tail(val);
* obj.add_at_index(index, val);
* obj.delete_at_index(index);
*/
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_link_list() {
let mut obj = MyLinkedList::new();
obj.add_at_head(32);
let ret_1: i32 = obj.get(0);
assert_eq!(ret_1, 32);
obj.add_at_head(31);
let ret_1: i32 = obj.get(0);
assert_eq!(ret_1, 31);
obj.add_at_head(30);
let ret_1: i32 = obj.get(0);
assert_eq!(ret_1, 30);
assert_eq!(vec![30,31,32], obj.debug_link_list());
obj.add_at_tail(33);
assert_eq!(vec![30,31,32,33], obj.debug_link_list());
//obj.add_at_head(val);
//obj.add_at_tail(33);
obj.add_at_index(0,29);
assert_eq!(vec![29,30,31,32,33], obj.debug_link_list());
obj.add_at_index(5,34);
assert_eq!(vec![29,30,31,32,33,34], obj.debug_link_list());
obj.add_at_index(3,35);
assert_eq!(vec![29,30,31,35,32,33,34], obj.debug_link_list());
obj.delete_at_index(3);
assert_eq!(vec![29,30,31,32,33,34], obj.debug_link_list());
obj.delete_at_index(0);
assert_eq!(vec![30,31,32,33,34], obj.debug_link_list());
obj.delete_at_index(4);
assert_eq!(vec![30,31,32,33], obj.debug_link_list());
//obj.delete_at_index(index);
}
}
here is all code, I used the unsafe blocks.
like this function:
fn get(&self, index: i32) -> i32 {
if self.length <= index {
return -1;
}
let mut i = 0;
//let mut head = Rc::clone(&self.head.as_ref().unwrap());
let mut head = &self.head;
//let mut borrow_cur:Ref<LinkNode>;
while let Some(t) = head {
//let node = t.borrow();
if i == index {
unsafe {
return (*t.as_ptr()).val;
}
}
i += 1;
//head = & node.next;
unsafe {
head = & (*t.as_ptr()).next;
}
}
-1
}
what I want is //let node = t.borrow(); and use //head = & node.next; to get the next linkednode. But the compiler said the node's lifetime is over at the end of block. But What I want is the next. The variable node is a Ref<LinkNode>, I want the head to point to the next not the node. So it should not. How to let it works other than use the unsafe block?
Please help me. I think it should pass while the compiler didn't.