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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
//1.设置last节点，last节点初始化的时候是在头结点的前一个节点，如果值不同，则让last节点往前走,cur节点页继续往前判断
//2.如果值相同，last节点不走，让cur节点往前走到节点没有重复的节点为止
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;
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseList = reverse(slow);
        ListNode cur1 = head;
        ListNode cur2 = reverseList;
        while(cur2!=null){
            if(cur1.val!=cur2.val){
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;

    }
    private ListNode reverse(ListNode node){
        if(node==null||node.next==null){
            return node;
        }
        ListNode cur = node;
        ListNode pre = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}