当前位置：首页 > news >正文

Leetcode 04 java

news 2025/7/19 15:56:11

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

题目

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" 这样的字符串。

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

复制链表到数组：首先，程序会把链表中的每个数字按顺序放到一个动态数组里。这是因为链表不像数组那样可以直接从后往前访问，所以我们需要先把链表的值存到数组中。
双指针法检查回文：然后，程序使用两个指针，一个从前向后移动，另一个从后向前移动。每次比较这两个指针指向的数字是否相同：
- 如果在任何时候发现两个指针指向的数字不一样，就说明这个链表不是回文链表，程序会立即返回false。
- 如果两个指针相遇了还没有发现不同的数字，就说明链表是回文链表，程序会返回true。