题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
提示：
-
链表中节点数目在范围[1, 105] 内
-
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
上一篇文章中我介绍了一个最简单的方法——使用集合。但这种方法会牺牲一些效率，因为 List 的操作通常比直接操作链表节点要慢，尤其是在涉及到频繁插入和删除操作时。此外，使用 List 会增加空间复杂度，因为你需要额外的空间来存储链表的元素。所以我又找到一个原地操作链表的高效算法，能实现时间复杂度为 O(n) 和 空间复杂度为 O(1) 。
首先，找到链表的中点并反转后半部分链表。接着，比较前半部分和反转后的后半部分是否相同。最后，根据比较结果返回 true 或 false。如果需要保持原链表的结构不变，可以在返回结果之前恢复链表的后半部分。
算法步骤：
-
找到链表的中点：使用快慢指针法，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针将位于链表的中点。
-
反转链表的后半部分：从中点开始反转链表的后半部分。
-
比较前半部分和反转后的后半部分：从链表的开始和中点开始，逐个比较节点的值，如果所有值都相同，则链表是回文的。
-
恢复链表（可选）：如果需要保持原链表的结构不变，可以再次反转链表的后半部分以恢复原链表。
-
返回结果：如果链表是回文的，返回 true；否则，返回 false。
复杂度：
-
时间复杂度：O(n)，其中 n 是链表的长度。
-
空间复杂度：O(1)，算法是原地进行的，不占用额外的空间（除了几个指针变量）。
我的 Java 代码：
class Solution {public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 步骤1: 找到链表的中点ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}// 步骤2: 反转链表的后半部分ListNode prev = null;while (slow != null) {ListNode Temp = slow.next;slow.next = prev;prev = slow;slow = Temp;}// 步骤3: 比较前半部分和反转后的后半部分ListNode firstHalf = head;ListNode secondHalf = prev;boolean isPalin = true;while (secondHalf != null) {if (firstHalf.val != secondHalf.val) {isPalin = false;break;}firstHalf = firstHalf.next;secondHalf = secondHalf.next;}// 步骤4: 返回结果return isPalin;}
}