0234.回文链表

https://leetcode.cn/problems/palindrome-linked-list/

一次遍历

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

在写该题目的 rust 解法时发现凭此时的代码水平只能借助数组辅助比较，具体代码见 rust tab。想要尽力实现类似其他语言一样在找到中间节点之后，反转后半部分链表的逻辑，但 rust 不可变性这一原则的存在限制了我的下一步工作。完美的解法让 copilot 来给我演示吧！

// 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
//     }
//   }
// }
impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        // find middle
        let mut fast = &head;
        let mut slow = &head;
        let mut nums1 = vec![];
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            let nt = &fast.as_ref().unwrap().next;
            fast = &nt.as_ref().unwrap().next;
            nums1.push(slow.as_ref().unwrap().val);
            slow = &slow.as_ref().unwrap().next;
        }
        let mut nums2 = vec![];
        while slow.is_some() {
            nums2.push(slow.as_ref().unwrap().val);
            slow = &slow.as_ref().unwrap().next;
        }
        nums2.reverse();
        for i in 0..nums1.len() {
            if nums1[i] != nums2[i] {
                return false;
            }
        }
        true
    }
}

impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        let mut values = Vec::new();
        let mut current = head;
        while let Some(node) = current {
            values.push(node.val);
            current = node.next;
        }
        let mut left = 0;
        let mut right = values.len() - 1;
        while left < right {
            if values[left] != values[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }
}

显然copilot 的代码(第二个rust tab)比我写的好看且简洁，但是空间复杂度并没有降低，仍旧需要调整。