数据结构：（牛客OR36）链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

 思路：创建新的数组，遍历原链表，将链表结点中的值放入数组，在数组中判断是否是回文结构

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// 创建新的数组int arr[900]={0};ListNode*pcur=A;int i=0;// 将链表结点中的值放入数组while(pcur){arr [i++]=pcur->val;pcur=pcur->next;}//找中间的结点，判断是否是回文数字int left=0;int right=i-1;while(left < right){if(arr[left]!=arr[right]){return false;}left++;right--;}return true;}
};