/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

#include <iterator>
#include <stack>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        //处理边界
        if(head==NULL||head->next==NULL)  return true;
        stack<ListNode*>s;
        //定义快慢指针
        ListNode* fast=head,*slow=head;
        while(fast&&fast->next)
        {
            s.push(slow);
            fast=fast->next->next;
            slow=slow->next;
        }
        if(fast!=NULL)
           slow=slow->next;
        while(!empty(s))
        {
            if(slow->val!=s.top()->val) return false;
            slow=slow->next;
            s.pop();
        }
        return true;
    }
};