题解 | #链表的回文结构#
链表的回文结构
http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
两种方法,第二种的话空间复杂度成O(N)了;;
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { if(A==NULL) return false; ListNode* slow=A,*fast=A; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } ListNode* cur=NULL,*next=slow; while(slow){ next=slow->next; slow->next=cur; cur=slow; slow=next; } next=A; while(cur){ if(next->val!=cur->val) return false; next=next->next; cur=cur->next; } return true; // write code here // if(A==NULL) // return false; // ListNode* cur=A; // vector<int> v; // while(cur){ // v.push_back(cur->val); // cur=cur->next; // } // for(int i=0;i<v.size()/2;i++){ // if(v[i]!=v[v.size()-i-1]) // return false; // } // return true; } };