每日编程-20170412

题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->2->1
返回：true

解答：

用栈即可，就是初次答链表，试一下

#include <stack>
using namespace std;

struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        bool answer = true;
        ListNode *p = A;
        stack<int> s;
        while (p)
        {
            s.push(p->val);
            p = p->next;
        }
        p = A;
        while (p)
        {
            if (s.top()!= p->val)
            {
                answer = false;
                break;
            }
            s.pop();
            p = p->next;
        }
        return answer;
    }
};