时间限制：3秒 空间限制：32768K 热度指数：7637

本题知识点：

题目描述

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

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

测试样例：

1->2->2->1

返回：true

1 /* 2 struct ListNode { 3     int val; 4     struct ListNode *next; 5     ListNode(int x) : val(x), next(NULL) {} 6 };*/ 7 class PalindromeList { 8 public: 9     bool chkPalindrome(ListNode* A) {10         // write code here11          if(A==NULL)   12              return true;  13         ListNode* slow;  14         ListNode* fast;  15         ListNode* temp;  16          17         slow=A;  18         fast=A;  19         20         while(fast->next!=NULL)  21              {  22                 temp=slow;   //temp用来存放最后mid之前的一个元素  23                 slow=slow->next;  24                 fast=fast->next;  25                 if(fast->next!=NULL)  26                      fast=fast->next;     27         }  28         if(mid==A)   29             return true;  //链表元素个数为1时；  30         ListNode* cur;  31   32         temp->next=NULL;     33         cur=slow->next;  34         slow->next=NULL;  35         36         while(cur!=NULL)  37             {  38                temp=cur->next;     39                cur->next=slow;  40                slow=cur;  41                cur=temp;  42         }  43           44         while(A!=NULL && slow!=NULL)  45             {  46                if(A->val==slow->val)  47                 {  48                    A=A->next;  49                    slow=slow->next;  50             }  51             else 52                 return false;  53         }  54        return true;  55        56     }57 };