题解 | #链表的回文结构#
链表的回文结构
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
大致思路:将中间结点之后的节点翻转,然后用一个头指针head和一个尾指针tail分别从前面和后面往中间遍历并进行值的比较。
步骤:求节点个数以及尾节点(最后比较用)->用节点个数的数学关系求翻转处的位置->将cur置于翻转处,prev记录cur前一个节点,next记录cur下一个结点->用三个指针将中间之后的节点进行翻转->最后从前后往中间遍历比较val。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ #include <cstddef> class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here //一个节点为回文直接返回 if(A->next==NULL){ return true; } //找尾节点顺便求长度 ListNode* tail=A; int len=1; while(tail->next){ len++; tail=tail->next; } //找翻转节点处 int pos=0; if(len%2==0){ pos=len/2+1; }else{ pos=len/2+2; } //将cur置于翻转处 ListNode* prev=NULL; ListNode* cur=A; ListNode* next=cur->next; while(--pos){ prev=cur; cur=next; next=next->next; } //进行翻转 while(true){ cur->next=prev; if(next==NULL){ break; } prev=cur; cur=next; next=next->next; } //头尾比较 ListNode* head=A; len=len/2; while(len--){ if(head->val!=tail->val){ return false; } } return true; } };