题解 | #链表的回文结构#
链表的回文结构
http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) {} };/ struct ListNode* middleNode(struct ListNode* head) { struct ListNode*slow,*fast; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
struct ListNode* reverseList(struct ListNode* head) {
struct ListNodecur=head; struct ListNodenewhead=NULL; while(cur) { struct ListNodenext=cur->next; //头插 cur->next=newhead; newhead=cur; //迭代往后走 cur=next; } return newhead; } class PalindromeList { public: bool chkPalindrome(ListNode A) { // write code here struct ListNodemid= middleNode(A); struct ListNoderHead=reverseList(mid); struct ListNodecurA=A; struct ListNodecurR=rHead; while(curA&&curR) { if(curA->val!=curR->val) { return false; } else { curA=curA->next; curR=curR->next; } } return true; } };
