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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
//时间复杂度O(n)  空间复杂度O(1)
public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        ListNode p1=head,p2=head;
        while(p2!=null&&p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;
        }
        //链表长度为奇数
        if(p2!=null){
            p1=p1.next;
        }
        //反转链表
        p1=reverseList(p1);
        p2=head;
        while(p1!=null){
            if(p1.val!=p2.val)
                return false;
            p1=p1.next;
            p2=p2.next;
        }
        return true;
    }
    
    public ListNode reverseList(ListNode head){
        if(head==null){
            return null;
        }
        ListNode curr=head,pre=null,next;
        while(curr!=null){
            next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }
        return pre;
    }
}