回文链表
【问题描述】给你一个带头结点的单链表，请你编写函数isPalindrome，判断该链表是否为回文链表。
如果是，返回true；否则，返回false。
其中函数createList，采用尾插入法创建含有头结点的单链表。
【输入形式】两行，第一行：单链表中元素个数n，第二行：以空格间隔的n个整数
【输出形式】单链表是回文链表，输出yes,否则输出no
【样例输入】
4
1 2 2 1
【样例输出】yes
【样例输入】
6
1 2 2 2 1 2
【样例输出】no
#include <iostream>
#include <stdlib.h>
using namespace std;
struct Node {
int data;
Node *next;
};
void createList(Node *&h,int n) {
Node *p,*r;
h=new Node;
h->next=NULL;
r=h;
for(int i=1; i<=n; i++) {
p=new Node;
cin>>p->data;
r->next=p;
r=p;
}
r->next=NULL;
}//尾插法创建带头结点的单链表
void printList(Node *h) {
Node *p;
p=h->next;
while(p) {
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}//输出单链表元素
//------借助栈，判断链表元素是否构成回文-------
typedef struct {
int* base;
int* top;
} sqstack;
void initStack(sqstack &s) {
s.base=(int*)malloc(10*sizeof(int));
s.top=s.base;
}//顺序栈的初始化
void push(sqstack &s,int e) {
*s.top++=e;
}//进栈
void pop(sqstack &s,int &e) {
e=*--s.top;
}//出栈
int isEmpty(sqstack s) {
if(s.top==s.base) return 1;
else return 0;
}//判断是否为空
int getLength(Node* h) {
Node* p=h;
int count=0;
while(p->next) {
count++;
p=p->next;
}
return count;
}//获取链表中元素数量
int isPalindrome(Node *h) {
Node *p=h->next;
sqstack s;
initStack(s);
for(int i=0; i<getLength(h); i++) {
push(s,p->data);
p=p->next;
}//链表元素入栈
p=h->next;
int e;
while(!isEmpty(s)) {
pop(s,e);
if(e==p->data) p=p->next;
//出栈，比较下一个数字
else return 0;
//若某次比较失败，返回0，不是回文链表
}
return 1;//全部比较成功，是回文链表
}
//--------------------------------
int main() {
int n;
Node *h;
cin>>n;
createList(h,n);
cout<<(isPalindrome(h)?"yes":"no");
return 0;
}
记录一些数据结构学习过程的习题代码，便于日后查看。如有错误，欢迎交流指正。