一、题目
函数原型：
bool chkPalindrome(ListNode* A)
二、思路
判断一个单链表是否为回文结构，由于单链表不能倒序遍历，所以需要找到单链表的后半段，并将其逆置，再与前半段链表进行比较。
如何找到单链表的后半段呢？
如果链表结点数为偶数个，只要找到单链表的第二个中间结点即可。
如果链表节点数为奇数个，只要找到单链表中间结点的下一个结点即可。
本题相关题目：
相关题解：
三、代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ #include <cstddef> ListNode* reserve(ListNode *pphead)//逆置链表函数 { if(pphead==NULL||pphead->next==NULL) return pphead; else { ListNode *prev =NULL; ListNode *cur=pphead; ListNode *next=pphead->next; while(cur) { cur->next=prev; prev=cur; cur=next; if(next) next=next->next; else next=NULL; } return prev; } } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here ListNode *fast=A; ListNode *slow=A; while(fast)//找链表的第二个中间结点或链表中间结点的下一个结点 { slow=slow->next; if(fast->next) fast=fast->next->next; else fast=NULL; } //逆置链表 // ListNode *B=NULL; // ListNode *tailB=NULL; // while(slow) // { // if(tailB==NULL) // { // B=tailB=slow; // } // else // { // tailB->next=slow; // tailB=slow; // } // slow=slow->next; // } // tailB->next=NULL; ListNode *B=reserve(slow);//逆置链表 ListNode *curA=A; ListNode *curB=B; while(curA&&curB)//比较前半段和后半段链表 { if(curA->val==curB->val) { curA=curA->next; curB=curB->next; } else return false; } return true; } };
