题解 | #链表的回文结构#
链表的回文结构
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here struct ListNode* slow,*fast,*mid,*cur,*insertnode,*head; slow=fast=A; mid=insertnode=head=NULL; //找中间节点 while(fast&&fast->next) //cur->next判断奇数链表尾,cur判断偶数链表尾 { slow=slow->next; fast=fast->next->next; } mid=slow; //mid把原始链表分为左链表,右链表(包括mid) //逆转右链表 cur=mid->next; head=mid; while(cur) { //头插,将cur插入head前,并后置cur insertnode=cur; cur=cur->next; insertnode->next=head; head=insertnode; } mid->next=NULL; //开始比较 while(A&&head) { if(A->val!=head->val) { return false; } else { A=A->next; head=head->next; } } return true; } };