牛客网新出了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。
题单地址：https://www.nowcoder.com/link/pc_kol_wsx
一、题目描述
给你一个单链表的头节点 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) 空间复杂度解决此题？
二、题目解析
1、使用快慢指针寻找出单链表的中间结点来，通过这个中间结点，可以把单链表划分为两个部分。
2、左部分包含了中间结点，右部分不包含中间结点。
3、使用迭代法反转右边部分。
4、设置两个指针，一个指向链表的头节点，一个指向反转成功之后的右部分的头结点。
5、让这两个指针向内部移动，对比它们指向的结点值，如果发现结点值相同，继续向内移动，如果不相同，则可以直接返回 false。
三、参考代码
class Solution {
public boolean isPalindrome(ListNode head) {
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode leftEnd = middleNode(head);
// 反转链表
ListNode rigthStart = reverseList(leftEnd.next);
// 判断是否回文
ListNode a = head;
ListNode b = rigthStart;
boolean result = true;
while (result && b != null) {
if (a.val != b.val) {
result = false;
}
a = a.next;
b = b.next;
}
return result;
}
// 迭代方法进行反转链表
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 获取链表的中间节点
private ListNode middleNode(ListNode head) {
// 设置两个指针，一开始都指向链表的头节点
ListNode slow = head;
ListNode fast = head;
// 接下来，让这两个指针向前移动
// 如果可以移动，那么就会让快指针每次移动两步，慢指针每次移动一步
// 而快指针可以移动两步的前提就是当前节点不为空，同时下一节点也不为空
// 这样才能保证 fast.next 有值、fast.next.next 有值
while(fast.next != null && fast.next.next != null){
// 慢指针每次移动一步
slow = slow.next;
// 快指针每次移动两步
fast = fast.next.next;
}
// 最后，slow 指向的就是中间节点
return slow;
}
}
