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

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
        if (head == null || head.next == null) {
            return true;
        }

        //0、两个节点起步
        //1、快慢节点确定中点
        //2、反转链表后半段
        //      偶数节点从slow开始反转，断开prev->slow
        //      奇数节点从slow.next开始反转，断开prev->slow, slow->slow.next
        //3、两头向中间对比

        //快慢指针扫
        ListNode slow = head;
        ListNode fast = head;
        ListNode start = null;
        ListNode prev = null;

        while (fast.next != null) {
            //右移
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;

            //偶数情况，最少从2个节点起步
            if (fast == null) {
                start = slow;
                break;
            }
        }

        //start未被赋值，为奇数情况，slow正好为中点，从下一个开始反转
        if (start == null) {
            start = slow.next;
            //断开slow向后的指针
            slow.next = null;
        }

        //断开slow前一个节点指向slow 的指针
        if (prev != null) {
            prev.next = null;
        }

        //开始反转链表
        prev = null;
        ListNode tmp = null;
        while (start != null) {
            tmp = start.next;

            start.next = prev;

            prev = start;
            start = tmp;
        }

        ListNode tail = prev;
        while (tail != null && head != null) {
            if (tail.val != head.val) {
                return false;
            }
            tail = tail.next;
            head = head.next;
        }

        return true;

    }
}