【数据结构】【链表代码】 回文

利用快慢指针

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode*newHead=NULL;struct ListNode*cur=head;while(cur){struct ListNode*next=cur->next;//头插cur->next=newHead;newHead=cur;cur=next;}return newHead;
}
class PalindromeList {public:bool chkPalindrome(ListNode* A) {ListNode* fast = A;ListNode* slow = A;ListNode*prev=NULL;//就算逆置了，但是逆置的第一个元素，它的前面的元素的next域还是指向逆置的第一个元素while (fast && fast->next) {prev=slow;//因为从slow开始进行逆置slow = slow->next;fast = fast->next->next;}prev->next=NULL;因为从slow开始进行逆置，逆置后slow变成最后一个元素slow=reverseList(slow);while(A){if(A->val!=slow->val){return false;}else{A=A->next;slow=slow->next;}}}
};