判断链表的全部n个字符是否中心对称。

设单链表的表头指针为L，结点结构由data和next两个域构成，其中data域为字符型。试设计算法判断链表的全部n个字符是否中心对称。例如XYX，XYYX是中心对称。

思想：先求链表长度，然后将前n/2个元素入栈，将栈顶元素与后n/2个元素进行比较，如果栈为空则对称。链表为n个元素时，去掉中间元素再进行比较。

代码：

typedef struct{
char *data;
int top;
}SqStack;
 //求带头结点链表的长度 
int length(LinkList L){
int len=0;
L=L->next;
while(L!=NULL){
L=L->next;
len++;
} 
return len;
}
//判断带头结点的链表是否对称 
bool issymmetry(LinkList L){
int len=length(L);//求链表长度
if(length==0||length==1) return true;

//初始化栈  
SqStack stack;
stack.data=(char*)malloc(sizeof(char)*(length/2));
stack.top=-1;

// 入栈
LNode *p=L->next;
for(int i=0;i<length/2;i++){
stack.data[++stack.top]=p->data;
p=p->next;
} 

if(length%2==1) p=p->next;//舍弃中间元素

//出栈进行比较
while(stack.top > -1){
if(stack.data[stack.top]==p->data){
stack.top--;
p=p->next;
}else{//不对称 
break;
}
} 
return stack.top==-1;//栈空，则说明对称 
}

时间复杂度O（n）；空间复杂度O（1）

原文地址：https://blog.csdn.net/m0_56332819/article/details/142289451

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！