Leetcode 04 java

坚持坚持坚持！！！！呵呵额呵呵不想学了，坚持坚持坚持坚持坚持！！！！

题目

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题解

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 创建一个动态数组vals，用于存储链表中的所有节点值
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;  // 初始化当前节点为头节点
        while (currentNode != null) {  // 遍历链表直到末尾
            vals.add(currentNode.val);  // 将当前节点的值添加到数组中
            currentNode = currentNode.next;  // 移动到下一个节点
        }

        // 使用双指针法判断数组是否是回文结构
        int front = 0;  // 前指针初始化为数组的起始位置
        int back = vals.size() - 1;  // 后指针初始化为数组的末尾位置
        while (front < back) {  // 当两个指针还未相遇时
            // 如果前指针和后指针所指的元素不相等
            if (!vals.get(front).equals(vals.get(back))) {
                return false;  // 说明不是回文，返回false
            }
            front++;  // 前指针向后移动一位
            back--;   // 后指针向前移动一位
        }
        return true;  // 如果所有元素都匹配，则返回true
    }
}

通俗解释

这个程序是用来判断一个链表是否是回文链表的。回文链表的意思是，链表中的元素从前往后读和从后往前读是一样的，就像 "1221" 或者 "racecar" 这样的字符串。

程序的工作流程是这样的：

1. 复制链表到数组：首先，程序会把链表中的每个数字按顺序放到一个动态数组里。这是因为链表不像数组那样可以直接从后往前访问，所以我们需要先把链表的值存到数组中。

2. 双指针法检查回文：然后，程序使用两个指针，一个从前向后移动，另一个从后向前移动。每次比较这两个指针指向的数字是否相同：

   • 如果在任何时候发现两个指针指向的数字不一样，就说明这个链表不是回文链表，程序会立即返回false。
   • 如果两个指针相遇了还没有发现不同的数字，就说明链表是回文链表，程序会返回true。

进阶思考

这种方法的时间复杂度是 O (n)，因为我们需要遍历链表一次，然后再遍历数组一次。空间复杂度也是 O (n)，因为我们需要一个数组来存储链表的所有元素。

如果要达到 O (1) 的空间复杂度，我们可以：

1. 找到链表的中间点
2. 反转后半部分链表
3. 比较前半部分和反转后的后半部分
4. 恢复链表（可选）

但这些步骤会让代码变得更复杂，而当前提供的方法已经足够简单易懂了。

我觉得不是很难理解，就是自己写会写不出来，然后后面如果会反转链表的操作，这道题目还可以自己琢磨一下！