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

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        // 遍历一遍求长度
        int n = 0;
        for (auto p = head; p ; p = p->next) n++;
        if (n < 2) return true;
        stack<int> stk;
        auto p = head;
        for (int i = 0; i < n >> 1; i++) {
            stk.push(p->val);
            p = p->next;
        }
        if (n & 1) {// 奇数个中间数不管
            p = p->next;
        }
        while (p) {
            if (stk.top() == p->val) {
                stk.pop();
                p = p->next;
            }
            else return false;
        }
        if (stk.size()) return false;
        return true;
    }
};