题解 | #链表的回文结构#

这道题上写着知识点是链表和栈，那么我们可以利用栈来解决这道题

时间复杂度为O(N) 空间复杂度为O(N)

import java.util.*;
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        Stack<Integer> stack = new Stack<>();
        ListNode B=A;
        int count1=0;
        int count2=0;
        //遍历链表，得到链表长度
        while(B!=null){
            count1++;
            B=B.next;
        }
        count1/=2;
        count2=count1;
        //遍历一半链表，将链表元素入栈
        while(count1>0){
            count1--;
            stack.push(A.val);
            A=A.next;
        }
        //遍历后半部分链表
        while(count2>0){
            count2--;
            //如果链表元素和出栈元素相等，继续遍历，直到遍历结束
            if(stack.pop()==A.val){
                A=A.next;
            }else{//如果链表元素与出栈元素不相等，直接返回false
                return false;
            }
        }
        return true;
    }
}