## 问题描述 > 试写一算法来判断单链表的前n个字符是否中心对称。 例如xyx，xyyx都是中心对称 ## 算法思想 > 在[第1章第2节练习题19 判断循环双链表对称](http://blog.csdn.net/u013595419/article/details/50511050)中已经初次涉及到了判断链表中心对称的问题，但是因为单链表只能从前往后遍历，因此不能使用与其相同算法进行解决，那么借助栈来判断单链表中的数据是否中心对称。 > 将单链表的前一半元素依次入栈，遍历到单链表的后一半元素的第一个元素时，便从栈中弹出一个元素，对它们俩开始比较。 > - 若相等，则将链表中的下一个元素与栈中再次弹出的元素进行比较，直至单链表到末尾，而且如果此时栈也为空栈，则可得出此单链表是中心对称的结论； > - 若不相等，则单链表不是中心对称。 ## 算法描述 ~~~ int JudgeSym(LNode* head,int n) { LNode *p=head->next; char s[n/2]; int i; for(i=0;i<n/2;i++){ s[i]=p->data; p=p->next; } i--; if(n%2){ p=p->next; } while(p&&p->data==s[i]){ p=p->next; i--; } if(i==-1){ return 0; }else{ return -1; } } ~~~ 具体代码见附件。 ## 附件 ~~~ typedef char ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); int JudgeSym(LNode*,int); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=CreatList(head); Print(head); int flag; int n=5; flag=JudgeSym(head,n); if(flag){ printf("The link is not symmetery before %d charactor!\n",n); }else{ printf("The link is symmetery before %d charachtor!\n",n); } return 0; } //尾插法建立单链表 LinkList CreatList(LNode* head) { LNode *L; LNode *r=head; ElemType x; scanf("%c",&x); while(x!='\n'){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%c",&x); } return head; } //判断中心对称 int JudgeSym(LNode* head,int n) { LNode *p=head->next; char s[n/2]; int i; for(i=0;i<n/2;i++){ s[i]=p->data; p=p->next; } i--; if(n%2){ p=p->next; } while(p&&p->data==s[i]){ p=p->next; i--; } if(i==-1){ return 0; }else{ return -1; } } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4c",p->data); p=p->next; } printf("\n"); } ~~~