力扣234.回文链表
给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：链表中节点数目在范围[1, 105]内0 <= Node.val <= 9
题目解读
回文链表：本质是单链表的一种特殊结构 —— 从链表头部到尾部遍历得到的节点值序列，和从尾部到头部遍历得到的序列完全一致，比如 "abba"、"12321"，正读和反读都相同。我们往往使用这“对称性”解决问题。
思路一
将链表转换为数组后使用双指针判断是否是回文。
具体步骤与解析
1.统计链表长度
int len = 0;//用以储存链表长度 ListNode cur = head;//从头节点出发 while (cur != null) { len++; // 每遍历一个节点，长度+1 cur = cur.next; // 游标后移 } 作用：确定后续数组的长度，避免数组越界或浪费空间。
2.将链表值存入数组
cur = head; // 重置游标，回到链表头 int[] res = new int[len]; // 根据长度创建数组 for (int i = 0; i < res.length; i++) { res[i] = cur.val; // 存入当前节点值 cur = cur.next; // 游标后移 }注意：这里 for 循环的终止条件是 i < res.length，和链表长度完全匹配，不会遗漏或越界。
3.双指针判断回文
for (int i = 0, j = len - 1; i < j; i++, j--) { if (res[i] != res[j]) { // 对称位置值不等，直接返回false return false; } } return true; // 所有对称位置相等，是回文 } }左指针 i 从数组头部（i=0）开始，右指针 j 从数组尾部（j=len-1）开始,只要有一对值不相等，直接返回 false，反之若循环结束（i >= j）都未发现不相等，返回 true。
核心思路总结：先统计长度→再存值到数组→双指针判回文。
完整代码
class Solution { public boolean isPalindrome(ListNode head) { int len = 0; ListNode cur = head; while (cur != null) { len++; cur = cur.next; } cur = head; int[] res = new int[len]; for (int i = 0; i < res.length; i++){ res[i] = cur.val; cur = cur.next; } for (int i = 0, j = len - 1; i < j; i++, j--){ if (res[i] != res[j]){ return false; } } return true; } }思路二
先使用快慢指针找到链表中点将链表分为两个部分，再将后部分链表反转与前部分一一对应来判断回文链表。
具体步骤与解析
1.处理边界情况
if (head == null || head.next == null) return true;空链表 或 只有 1 个节点的链表，本身就是回文，直接返回 true。
2.快慢指针找链表中点
while (fast != null && fast.next != null) { pre = slow; // 记录slow的前一个节点（分割点） slow = slow.next; // 慢指针走1步 fast = fast.next.next;// 快指针走2步 }慢指针（slow）每次走 1 步，快指针（fast）每次走 2 步，当 fast 走到链表末尾时，slow 恰好走到链表后半段的起点，pre 始终记录 slow 的前一个节点，用于后续分割链表。
3.分割链表 + 反转后半段
pre.next = null; // 切断前半段和后半段的连接 // 前半段链表的头 ListNode cur1 = head; // 反转后半段链表，得到反转后的头 ListNode cur2 = reverseList(slow); 辅助方法（reverseList）
ListNode reverseList(ListNode head) { ListNode tmp = null; // 临时存储下一个节点 ListNode pre = null; // 记录当前节点的前一个节点 while (head != null) { tmp = head.next; // 先保存下一个节点，避免断链 head.next = pre; // 当前节点指向前一个节点（反转） pre = head; // pre后移到当前节点 head = tmp; // head后移到原本的下一个节点 } return pre; // 反转后的链表头 } }
4.对比前后两段链表
while (cur1 != null) { if (cur1.val != cur2.val) { return false; } cur1 = cur1.next; cur2 = cur2.next; } return true; }逐一比较两个链表的节点，值只要有一个值不相等，就不是回文；全部相等则是回文。
完整代码
class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = null; } } class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head; ListNode pre = head; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; ListNode cur1 = head; ListNode cur2 = reverseList(slow); while (cur1 != null) { if (cur1.val != cur2.val) { return false; } cur1 = cur1.next; cur2 = cur2.next; } return true; } ListNode reverseList(ListNode head) { ListNode tmp = null; ListNode pre = null; while (head != null) { tmp = head.next; head.next = pre; pre = head; head = tmp; } return pre; } }
