#[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
    }
  }
}

struct Solution {}
impl Solution {
    pub fn is_palindrome(mut head: Option<Box<ListNode>>) -> bool {
        let mut dummy = &head;
        let mut len: usize = 0;
        while dummy.is_some() {
            len += 1;
            dummy = &dummy.as_ref().unwrap().next;
        }

        if len <= 1 { return true; }

        let mut first = &mut head;
        let mut second;
        let mid = len / 2;

        for _ in 1..mid {
            first = &mut first.as_mut().unwrap().next;
        }

        if len % 2 == 0 {
            second = first.as_mut().unwrap().next.take();
        } else {
            // remove the middle node
            let tmp = first.as_mut().unwrap().next.take();
            second = tmp.unwrap().next.take();
        }

        // now reverse first linked list
        let mut prev = None;
        let mut cur = head;
        let mut next;
        while cur.is_some() {
            let mut node = cur.unwrap();
            next = node.next.take();
            node.next = prev;
            prev = Some(node);
            cur = next;
        }

        // now compare first and second
        // note that prev becomes the head node of first
        while prev.is_some() && second.is_some() {
            let node1 = prev.unwrap();
            let node2 = second.unwrap();
            if node1.val != node2.val {
                return false;
            } else {
                prev = node1.next;
                second = node2.next;
            }
        }

        // prev.is_none() && second.is_none()
        true
    }
}