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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/*将链表的分为两部分，后部分放入栈，一次对比。*/
class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        ListNode *p = head;
        int len = 0;
        while (p) {
            len++;
            p = p->next;
        }
        int len1 = 0;
        if(len % 2 == 0) len1 = len / 2; //偶数
        else len1 = (len + 1) / 2; //奇数
        ListNode *p1 = head;
        ListNode *p2 = head;
        for(int i =0;i < len1; i++){
            p2 = p2->next;
        }
        stack<int> s;
        while(p2){
            s.push(p2->val);
            p2=p2->next;
        }
        while(!s.empty() && p1->val == s.top()){
            p1 = p1->next;
            s.pop();
        }
        if(s.empty()) return true;
        else return false;
    }
};