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

import java.util.*;

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

// 这里不能采用直接反转比较的方法，因为直接反转会改变整体next结构，导致你想正向反向比较的链表next一致
// 但是我们可以采用只反转后半段来进行判断！！！
public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {

        // 双指针得到中点
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow就是中点，反转，然后将fast设为head，开始判断
        slow = reserve(slow);
        fast = head;

        while(slow != null && fast != null){
            if(fast.val != slow.val){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return true;
    }

    // 反转函数
    public ListNode reserve(ListNode head){

        ListNode preNode = null;
        ListNode nextNode = null;

        while(head != null){

            nextNode = head.next;

            head.next = preNode;

            preNode = head;

            head = nextNode;

        }

        return preNode;

    }
}