C++数据结构与算法之判断一个链表是否为回文结构的方法
本文实例讲述了C++判断一个链表是否为回文结构的方法。分享给大家供大家参考，具体如下：
题目：
给定一个链表头节点head，请判断是否为回文结构
例如：
1->2->1true
1->2->2->1true
1->2->3->4->2->1false
解题思路及代码
1、找到链表中间节点，然后将链表中间节点的右边所有节点放入一个栈中。
2、然后从链表首节点和栈顶元素一一对比，不相等则returnfalse。
算法C++代码：
链表节点结构定义
typedefstructNode
{
intdata;
structNode*next;
}node,*pLinkedList;
boolisHuiWen(pLinkedListhead)
{
if(head==NULL||head->next==NULL)
returntrue;
pLinkedListright=head->next;//保存中间节点的下一个节点(若为偶数则为偏右的中间节点)
pLinkedListcur=head;//快指针
while(cur->next!=NULL&&cur->next->next!=NULL)
{
right=right->next;
cur=cur->next->next;
}
//当链表总结点个数为奇数情况时：
if(cur->next!=NULL&&cur->next->next==NULL)
right=right->next;
//将链表右边的节点放入一个栈中
stack*s=newstack();
while(right!=NULL)
{
s->push(right);
right=right->next;
}
//比较链表左右两边节点是否相等
while(!s->empty())
{
if(head->next->data!=s->top()->data)
returnfalse;
s->pop();
head=head->next;
}
returntrue;
}
希望本文所述对大家C++程序设计有所帮助。