题解 | #判断一个链表是否为回文结构#

基本思路

一个链表是回文的说明从前往后遍历链表和从后往前遍历链表的结果是相同的，但是要实现从后往前遍历链表就需要新建一个反转链表存放原链表的所有节点，所以还是需要先遍历一遍原链表，将里面的节点取出，那这样的话直接将链表中的节点取出放到数组后，用双指针从前往后和从后往前遍历数组就更方便了，不需要新建一个链表。

回文链表一般从前往后遍历到中点和从后往前遍历到中点是一致的，所以想办法定位到链表的中点，反转后半部分的链表再同时遍历前半部分的链表和后半部分的链表看看是否一致即可，找到链表中点的方法可以用快慢指针，快指针每次走两个节点，慢指针每次走一个节点，当快指针走到终点时，慢指针走到了中点。

参考

参考题解

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    private ListNode reverse(ListNode head) {
        ListNode current = head;
        ListNode pre = null;
        ListNode temp = null;

        while (current != null) {
            temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }

        return pre;
    }
    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;

        // 快指针到达终点时，慢指针到达中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        slow = reverse(slow); // 反转中点往后的链表
        fast = head;  // fast指向前半部分链表的开头

        while (slow != null) {  // 由于两半部分链表的长度相同，所以slow到达终点时，fast也到了前半部分链表的终点
            if (slow.val != fast.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }
}