判断单链表的前n个元素是否对称

问题描述：

设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的前n个字符是否中心对称。例如xyx、xyyx都是中心对称。

问题解答：

算法思想：使用栈来判断链表中的数据是否中心对称。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中下一个元素与栈中再弹出的元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。

int dc(LinkList L, int n){
    //h是带头结点的n个元素单链表，本算法判断链表是否是中心对称
    char s[n/2];int i=1;  //i记结点个数，s字符栈
    P=L->next;  //p是链表的工作指针，指向待处理的当前元素
    for{i=0;i<n/2;i++) {  //链表前一半元素进栈
        s[i]=p->data;
        p=p->next;
    }
    i--;  //恢复最后的i值
    if(n%2==1)  //若n是奇数，后移过中心结点
        p=p->next;
    while(p!=NULL && s[i] ==p->data) { //检测是否中心对称
        i--;  //i充当找顶指针
        p=p->next;
    }
    if (i==-1)    //桟为空找
        return 1;    //链表中心对称
    else
        return 0;    //链表不中心对称
}

算法先将“链表的前一半”元素（字符）进栈。当n为偶数时，前一半和后一半的个数相同；当n为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出while循环，不再进行比较。

本题也可以先将单链表中的元素全部入栈，然后再次扫描单链表L并比较，直到比较到单链表L尾为止，但是算法需要两次扫描单链表L，效率不及上述算法高。