【Leetcode Top 100】234. 回文链表

问题背景

给你一个单链表的头节点 $head$，请你判断该链表是否为 回文链表（回文 序列是向前和向后读都相同的序列）。如果是，返回 $true$；否则，返回 $false$。

数据约束

• 链表中节点数目在范围 $[1,10^5]$ 内
• $0\le Node.val\le 9$

解题过程

非常经典的套路，先用快慢指针求出链表的中间节点，再从中间节点开始反转链表，最后从头开始和反转后的链表比对是否相等即可。

虽然题目没有要求，判断的题最好不要修改输入，所以最后再把链表反转回来。

具体实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {// 快慢指针求中间节点ListNode middle = middle(head);// 从中间节点开始反转middle = reverse(middle);ListNode check1 = head, check2 = middle; // 存一下两个指针，防止丢失while(check2 != null) {if(check1.val != check2.val) {return false;}check1 = check1.next;check2 = check2.next;}// 把链表反转回来middle = reverse(middle);return true;}private ListNode middle(ListNode head) {ListNode slow = head, fast = head;// 模板化的判断非空，慢指针走一步同时快指针走两步，最后慢指针会停在链表中点处while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private ListNode reverse(ListNode head) {// 初始化三个指针，分别指向头节点和它的前后节点// 由于循环中会率先更新 next 指针，这个变量可以不初始化ListNode pre = null, cur = head, next;while(cur != null) {// 反转操作next = cur.next;cur.next = pre;// 轮转指针pre = cur;cur = next;}return pre; // 注意要返回 pre}
}