回文链表
难度:
标签:
题目描述
给你一个单链表的头节点 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) 空间复杂度解决此题？
代码结果
运行时间: 76 ms, 内存: 24.8 MB
/*
* 判断单链表是否为回文链表
* 思路：
* 1. 使用流的方式将链表元素收集到列表中。
* 2. 使用双指针法从列表两端向中间比较。
*/
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; this.next = null; }
}
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// 将链表元素收集到列表中
List<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
// 使用双指针法比较列表两端的元素
int left = 0, right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) return false;
left++;
right--;
}
return true;
}
}解释
方法:
该题解的思路是将链表分为两半，反转后半部分链表，然后同时遍历前半部分和反转后的后半部分，依次比较对应节点的值是否相等。首先通过快慢指针找到链表的中点，慢指针每次走一步，快指针每次走两步，当快指针到达链表尾部时，慢指针刚好到达中点。如果链表节点数为奇数，则中点后一个节点才是后半部分的起点。然后反转后半部分链表，再同时遍历比较两个链表的节点值是否相等，如果都相等则说明是回文链表，否则不是回文链表。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在找到链表中点时，快慢指针的策略是如何确保慢指针停在正确的中点位置，特别是在链表长度为奇数和偶数时的具体差异是什么？
▷🦆
在反转链表部分，如何处理只有一个节点的情况，以及这种情况下反转后的链表头是什么？
▷🦆
您提到如果链表节点数为奇数，则中点后一个节点才是后半部分的起点，为什么需要跳过中点，它对回文结构的影响是什么？
▷🦆
在比较两个链表的节点值时，比较结束的条件是什么？为什么不需要同时检查左半部分链表是否也已遍历完毕？
▷相关问题
回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121 输出：true
示例 2：
输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
进阶：你能不将整数转为字符串来解决这个问题吗？
验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。
示例 3：
输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
提示：
1 <= s.length <= 2 * 105s仅由可打印的 ASCII 字符组成
