1 題目

已知長度為n（n>1）的單鏈表，表頭指針為L，結點結構由data和next兩個域構成，其中data域為字符型，設計一個在時間和空間兩方面都盡可能高效的算法，判斷該單鏈表是否中心對稱（例如xyx，xxyyxx都是中心對稱）。

2 思路

2.1 思路一

把單鏈表的后半段依此存入棧中，然后遍歷單鏈表的前半段，每遍歷一個元素，就從棧中彈出一個元素，進行比較，如果值不相等，則該鏈表為非對稱鏈表，否則，當棧為空時，則該鏈表為對稱鏈表。

例1: 對于單鏈表”xyzzyx”，把后半段yxx依次存入棧中，棧中為xyz，依次遍歷單鏈表的前半段xyz，遍歷x時，比較棧頂元素x；遍歷y時，比較棧頂元素y；遍歷z時，比較棧頂元素z，直到棧空，然后該鏈表為對稱鏈表。

例1: 對于單鏈表”xyzwqyx”，把后半段yxx依次存入棧中，棧中為xyz，依次遍歷單鏈表的前半段xyz，遍歷x時，比較棧頂元素z；遍歷y時，比較棧頂元素y；遍歷z時，比較棧頂元素q，值不相等，然后該鏈表為非對稱鏈表。

2.2 思路二

把單鏈表的后半段原地逆置，然后使用雙指針p、q依次遍歷單鏈表的前半段和后半段，若相等，則將p、q指向下一個元素，當q指向空指針時，該鏈表為對稱鏈表；否則該鏈表為非對稱鏈表。

2.3 考點

棧、頭插法

2.4 擴展

思考：當鏈表長度未知時，該怎么求？

• 1，思路一：遍歷單鏈表得到長度，按照原方法。
• 2，思路二：把單鏈表依次存入棧和入隊列，然后依次出棧和出隊列，比較元素。

3 實現

3.1 思路1

int judge1(LinkList L, int n){LNode* stack = new LNode[n/2];int index = -1;LNode *q = L->next, *p = L->next;for(int i = 1;i < (n+1)/2 + 1;i++){//偶數找對半下一個（4+1)/2+1 = 3//奇數找對半下兩個 (5+1)/2+ 1 = 4q = q->next;}while(q != nullptr){stack[++index] = *q;q = q->next;}//打印棧中的數據
//    while(index != -1){
//        printf("%c ",stack[index--].data);
//    }while(index != -1){if(p->data != stack[index--].data)return 0;p = p->next;    }return 1;
}

時間復雜度：O(n)
空間復雜度：O(n)

3.2 思路2

int judge2(LinkList L, int n){LNode *p = L->next, *q = L->next, *r;for(int i = 1;i < (n+1)/2;i++){q = q->next;}p = q->next;q->next = nullptr;while(p != nullptr){r = p->next;p->next = q->next;q->next = p;p = r;}//printLNode(L); //測試打印棧p = L->next;q = q->next;while(q != nullptr){if(p->data != q->data){return 0;}p = p->next;q = q->next;}return 1;}

時間復雜度：O(n)
空間復雜度：O(1)

3.3 完整例子

#include<iostream>typedef struct LNode{char data;struct LNode *next;
}LNode,*LinkList;//尾插法創建鏈表
LinkList createList(LinkList &L,int n){//L = (LinkList)malloc(sizeof(LNode));L = new LNode;LNode *s, *r= L;char x[n + 1];scanf("%s", x);int index = 0;while(n--){s = new LNode;s->data = x[index++];r->next = s;r = s;}r->next = nullptr;return L;
}//打印鏈表
void printLNode(LNode* L){LNode* p = L->next;while(p != nullptr){printf("%c ", p->data);p = p->next;}printf("\n");
}int judge1(LinkList L, int n){LNode* stack = new LNode[n/2];int index = -1;LNode *q = L->next, *p = L->next;for(int i = 1;i < (n+1)/2 + 1;i++){//偶數找對半下一個（4+1)/2+1 = 3//奇數找對半下兩個 (5+1)/2+ 1 = 4q = q->next;}while(q != nullptr){//棧中存儲數據stack[++index] = *q;q = q->next;}//打印棧中的數據
//    while(index != -1){
//        printf("%c ",stack[index--].data);
//    }while(index != -1){if(p->data != stack[index--].data)return 0;p = p->next;    }return 1;
}int judge2(LinkList L, int n){LNode *p = L->next, *q = L->next, *r;for(int i = 1;i < (n+1)/2;i++){//遍歷到后半段的前一個結點q = q->next;}p = q->next;//存儲后半段的頭指針的下一個結點（以防斷鏈）q->next = nullptr;//（后半段的頭指針下一個元素置空）while(p != nullptr){//使用頭插法原地逆置r = p->next;//防止斷鏈p->next = q->next;q->next = p;p = r;}//printLNode(L); //測試打印棧p = L->next;q = q->next;while(q != nullptr){if(p->data != q->data){return 0;}p = p->next;q = q->next;}return 1;}int main(){int n;scanf("%d", &n);//單鏈表長度（即字符串長度 ）LNode* L = new LNode[n];createList(L, n);printLNode(L);if(judge1(L, n) == 1) printf("對稱鏈表");else printf("非對稱鏈表");delete[] L;return 0;
}