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

利用栈的性质。将链表中一般的数据存放在栈中。

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

class Solution {
  public:
    /**
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        int len = 0, count = 0;
        stack<ListNode*> sk;
        ListNode* cur = head, *t = NULL;
        while (cur != NULL) {
            len++;
            cur = cur->next;
        }
        cur = head;
        count = len / 2;
        while (count--) {
            sk.push(cur);
            cur = cur->next;
        }
        if (len % 2 == 1) {
            cur = cur->next;
        }

        while (cur != NULL) {
            if (!sk.empty()) {
                t = sk.top();
                sk.pop();
            } else {
                break;
            }
            if (t->val != cur->val) {
                return 0;
            }
            cur = cur->next;
        }

        return 1;
    }
};