给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
方法1：使用栈解决
思路：使用栈先把链表的节点全部存放到栈中，然后再一个个出栈，这样就相当于链表从后往前访问了
其实我们只需要拿链表的后半部分和前半部分比较即可，没必要全部比较，所以这里可以优化一下
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>(); // 创建一个整数类型的栈，用于存储单链表中的节点值
ListNode temp = head; // 创建一个临时节点 temp，指向链表的头节点 head，用于遍历链表
int len = 0; // 初始化变量 len，用于记录链表的长度
// 遍历链表，将链表中的节点值依次压入栈中，并记录链表的长度
while (temp != null) {
stack.push(temp.val); // 将当前节点的值压入栈中
temp = temp.next; // 将指针移动到下一个节点
len++; // 长度加一
}
len >>= 1; // 计算链表的长度的一半。由于接下来是将栈中的值与链表的前半部分比较，因此只需要比较一半即可
// 循环比较链表前半部分与栈中的值
while (len-- >= 0) {
if (head.val != stack.pop()) // 如果链表前半部分的值与栈中弹出的值不相等，返回 false
return false;
head = head.next; // 将链表的指针指向下一个节点，继续比较
}
return true; // 如果循环结束，说明链表是回文的，返回 true
}
}
方法3：反转后半部分链表（牛逼）
思路： 通过找到链表的中间节点然后把链表后半部分反转，最后再用后半部分反转的链表和前半部分一个个比较即可
这段代码实现了判断给定的单链表是否是回文的功能。下面是对代码的详细解释：
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
// 通过快慢指针找到链表的中点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 如果 fast 不为空，说明链表的长度是奇数个，需要跳过中间节点
if (fast != null) {
slow = slow.next;
}
// 反转后半部分链表
slow = reverse(slow);
fast = head;
// 比较前半部分和后半部分的链表是否相等
while (slow != null) {
if (fast.val != slow.val)
return false;
fast = fast.next;
slow = slow.next;
}
return true;
}
// 反转链表
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
- 在
isPalindrome方法中，使用快慢指针找到链表的中点。如果链表长度是奇数，快指针fast会多走一步，此时slow指向的是中间节点的下一个节点。 - 然后将后半部分链表反转，并将反转后的头节点赋值给
slow。 - 最后，通过比较前半部分链表和反转后的后半部分链表的节点值是否相等，来判断链表是否是回文的。
reverse方法用于反转链表，采用迭代的方式实现。
