1. 题目链接

234. 回文链表 - 力扣（LeetCode）

2. 题目描述

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

3. 题目示例

示例 1 :

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

示例 2 :

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

4. 解题思路

1. 问题理解：
   • 判断一个单链表是否是回文链表
   • 回文链表：正读和反读都相同的链表
   • 示例：1→2→2→1 是回文链表；1→2→3 不是
2. 算法步骤：
   • 步骤1：使用快慢指针找到链表的中间节点
     • 快指针每次走两步，慢指针每次走一步
     • 当快指针到达末尾时，慢指针指向中间节点
   • 步骤2：反转后半部分链表
     • 从中间节点开始反转
     • 使用标准的链表反转方法
   • 步骤3：比较前后两部分链表
     • 同时遍历原链表前半部分和反转后的后半部分
     • 比较每个节点的值
3. 关键点：
   • 找到准确的中间节点（对于奇数长度和偶数长度都能处理）
   • 只反转后半部分链表，节省时间和空间
   • 比较时不需要考虑链表长度奇偶性，因为后半部分总是较短的部分

5. 题解代码

class Solution {public boolean isPalindrome(ListNode head) {// 1. 找到链表的中间节点ListNode mid = middleNode(head);// 2. 反转后半部分链表ListNode head2 = reverseList(mid);// 3. 比较前后两部分链表while (head2 != null) {if (head.val != head2.val) { // 发现不匹配的值return false;}head = head.next;head2 = head2.next;}// 所有值都匹配return true;}// 876. 链表的中间结点private ListNode middleNode(ListNode head) {// 快慢指针法找中间节点ListNode slow = head;ListNode fast = head;// 快指针每次走两步，慢指针每次走一步while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 当快指针到达末尾时，慢指针指向中间节点return slow;}// 206. 反转链表private ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {// 保存下一个节点ListNode nxt = cur.next;// 反转当前节点的指针cur.next = pre;// 移动pre和cur指针pre = cur;cur = nxt;}// 返回反转后的头节点return pre;}
}

6. 复杂度分析

1. 时间复杂度：
   • 找中间节点：O(n/2) ≈ O(n)
   • 反转后半部分：O(n/2) ≈ O(n)
   • 比较两部分：O(n/2) ≈ O(n)
   • 总时间复杂度：O(n)
2. 空间复杂度：
   • 只使用了常数个额外指针
   • 空间复杂度：O(1)