链表的回文结构。
题目描述：对于一个链表，请设计一个时间复杂度为O(n)，额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900.
分析如下：给两个指针，比较两个指针所在的元素的大小。
这是逆置的思想，下面我们来看代码吧！
class PalindromeList { public: //头插 ListNode* ReverseList(ListNode* pHead) { ListNode* pNewHead = NULL; ListNode* pCur = pHead; while(pCur) { pHead = pCur->next; pCur->next = pNewHead; pNewHead = pCur; pCur = pHead; } return pNewHead; } bool chkPalindrome(ListNode A) { //逆置的思想 if(NULL = A) return true; //找链表的中间位置 ListNode* pFast = A; ListNode* pSlow = A; ListNode* pSlowPre = NULL; while(pFast && pFast->next) { pFast = pFast->next->next; pSlowPre = pSlow; pSlow = pSlow->next; } pSlowPre->next = NULL;//置空 LiseNode* pCur1 = A; ListNode* PCur2 = ReverseList(pSlow); while(pCur1 && pCur2) { if(pCur1->val != pCur2->val) return false; pCur1 = pCur1->next; pCur2 = pCur2->next; } return true; } };我们来看一下另一种方法：
class PalindromeList { public bool chkPalindrome(ListNode A) { if(NULL == A) return true;//空链表直接返回 int* p = (int*)malloc(sizeof(int)*900);//给整形空间 //将链表中所有节点中的值放到辅助空间中 ListNode* pCur = A; int size = 0; while(pCur) { p[size++] = pCur->val; pCur = pCur->next; } //给定两个指针同时走，一个从头走，一个从尾走 int begin = p; int end = p+size-1; while(begin < end) { if(p[begin] != p[end]) { free(p); return false; } begin++; end--; } free(p); return true; } }
~bye~
