快慢指针 结合栈结构判断

第一步 定位

首先要找到中间位置，这里要注意区分奇数偶数个数

这里采用快慢指针来达到定位

第二步 压入栈

在慢指针向后迭代前让入栈

利用栈的先进后出的数据结构

第三步 比较

慢指针继续迭代，和栈头指针进行对比

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        if(head){
            if(!head->next){
                //只有一个数一定是回文数
                return true;
            }
            //快慢指针结合栈完成
            ListNode* fast = head;
            ListNode* slow = head;
            stack<int> temp;
            int ji = false;
            //第一步定位开始，考快指针到尽头
            while(fast){
                if(fast->next){
                    fast = fast->next->next;
                }else{
                    ji = true;
                    break;
                }
                //第二步压入栈
                temp.push(slow->val);
                slow = slow->next;
            }
            //奇数长度的需要慢指针迭代一次
            if(ji){
                slow = slow->next;
            }
            //开始回文判断
            while(slow){
                if(slow->val != temp.top()){
                    return false;
                }
                temp.pop();
                slow = slow->next;
            }
            return true;
            
        }
        return false;
    }
};