题解 | 链表的回文结构

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <stack>
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        string s,s1;ListNode* cur=A;
        while(cur)
        {
            s.push_back(cur->val+'0');
            s1.push_back(cur->val+'0');
            cur=cur->next;
        }
        reverse(s1.begin(),s1.end());
        return s==s1;

    }
};

解题思路：把链表的数字转成字符拼接到字符串中，然后和逆序后的字符串比较是否相等即可，时间复杂度O(2N)即O(N)