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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        // 可以将链表的后半部分反转，然后再跟前半部分比较是否一样
        // 反转链表在之前的入门里面已经写过

        // 链表为空，或者只有一个，是满足回文的，直接return，不然会出现程序越界问题
        if(head == null || head.next == null){
            return true;
        }
        ListNode slow = head , fast = head.next;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow就是中间值，偶数刚好是一半，奇数就是左半边，不包含中点
        // 但是我需要的是后半段的部分，需要再往前进一步，这样偶数就是下一半，奇数正好指向中间
        ListNode secondNode = reverseList(slow.next);
        while(secondNode != null ){
            if(head.val != secondNode.val){
                return false;
            }
            secondNode = secondNode.next;
            head = head.next;
        }
        return true;


        
    }
    private ListNode reverseList(ListNode head){
            ListNode pre = null, next = null;
            while(head != null ){
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            // 此时head为null
            return pre;
        }

   
}

题目包含两个部分，快慢指针找中点，反转链表。

需要注意的是，slow知道的是左半边的部分，要反转右半边，需要再加一。