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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
//1.链表数目为奇数或者偶数，都是通过快慢指针找到满指针最后指向的节点，然后反转包括slow指针指向的后面的节点
//2.然后再从反转的链表的头结点和原来链表的头结点开始遍历比较
//3.如果对应的值不一致，直接返回false,正常退出条件是反转的链表的指针不为null,然后返回true
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;
    }
}