静态网站建设规划,网站可免费做,linux用.net做网站,网站建设前的规划文章目录 1 题目2 思路2.1 思路一2.2 思路二2.3 考点2.4 扩展 3 实现3.1 思路13.2 思路23.3 完整例子 1 题目
已知长度为n#xff08;n1#xff09;的单链表#xff0c;表头指针为L#xff0c;结点结构由data和next两个域构成#xff0c;其中data域为字符型#xff… 文章目录 1 题目2 思路2.1 思路一2.2 思路二2.3 考点2.4 扩展 3 实现3.1 思路13.2 思路23.3 完整例子 1 题目
已知长度为nn1的单链表表头指针为L结点结构由data和next两个域构成其中data域为字符型设计一个在时间和空间两方面都尽可能高效的算法判断该单链表是否中心对称例如xyxxxyyxx都是中心对称。
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 (n1)/2 1;i){//偶数找对半下一个41)/21 3//奇数找对半下两个 (51)/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 (n1)/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 完整例子
#includeiostreamtypedef 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 (n1)/2 1;i){//偶数找对半下一个41)/21 3//奇数找对半下两个 (51)/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 (n1)/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;
}
