可以充值的网站怎么做,永久不收费免费的聊天软件,建网站找哪家公司,百度高级搜索入口#x1f493; 博客主页#xff1a;倔强的石头的CSDN主页 #x1f4dd;Gitee主页#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注
目录
一、问题描述
二、解题思路
三、C语言代码实现 一、问题描述 二、解… 博客主页倔强的石头的CSDN主页 Gitee主页倔强的石头的gitee主页 ⏩ 文章专栏《数据结构与算法 经典例题》C语言 期待您的关注
目录
一、问题描述
二、解题思路
三、C语言代码实现 一、问题描述 二、解题思路 回文结构Palindromic structure是指一个序列或字符串从前往后读和从后往前读是相同的。 计算机科学中回文结构可以出现在各种数据结构中如字符串、数组等。对于字符串来说判断一个字符串是否为回文字符串是一个常见的问题。判断方法是从字符串的两端开始比较字符是否相等如果都相等则继续比较下一对字符直到中间位置。如果在任何时刻存在一对不相等的字符则该字符串不是回文。 对于数组来说直接采取上述方法便可以判断是否是回文结构。但对于单链表来说则是行不通的因为单链表只能顺序访问不能随机访问。 判断单链表是否是回文结构的关键是对单链表中元素逐个比较的方法 这里给出的解决思路是:第一步:先求出链表的中间结点对于奇数个节点和偶数个节点的链表可以无差处理 第二步:将链表中间结点及以后的节点反转相当于链表的后半段构成了反转的新的链表 第三步:两个指针分别指向原链表的第一个节点和新链表的第一个节点 将两个指针指向的节点的数据进行比对这相当于从原链表的两端开始比对 如果节点的数据不同返回false 如果节点数据相同继续比对下一个直到任一指针指向空退出循环返回true 前两步需要单独封装两个函数分别是求链表的中间节点和反转链表 具体实现可以参考这两篇文章本文不再详细阐述 【数据结构与算法 刷题系列】求链表的中间结点-CSDN博客 【数据结构与算法刷题系列】C语言反转链表-CSDN博客 节点比较和移动的时候对于奇数个节点的链表和偶数个节点的链表处理方式和效果是相同的如图 奇数个节点的链表处理过程
1.初始链表 2.求得链表中间节点 3.将中间节点及之后的节点反转
需要注意
虽然链表后半部分的结构被反转next指针被改变
但中间节点的前一个节点的next指针未被改变依然指向初始的中间节点
4.比较过程
两个指针对比指向节点的值若相等各走一步 两个指针同时走向了NULL说明链表为回文结构 偶数个节点的链表处理过程
1.初始链表 2.求得链表中间节点 3.将中间节点及之后的节点反转 4.比较过程
两个指针对比指向节点的值若相等各走一步 有一个指针先走向了NULL说明链表是回文结构 由此也说明通过比较元素判断回文结构时有一个指针走向了NULL就已经完成了判断应当退出循环 三、C语言代码实现
//链表的回文结构
//对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。
//给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。
struct ListNode {int val;struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head) { //求链表的中间节点struct ListNode* slow, * fast; //创建快慢指针slow fast head; //初始化while (fast fast-next) { //当快指针可以移动两步时执行循环slow slow-next; //慢指针走一步fast fast-next-next; //快指针走两步}return slow;//遍历完成时slow所指节点就是中间节点
}
struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return head;//对空链表做特殊处理else {struct ListNode* n1, * n2, * n3;n1 NULL;n2 head;n3 n2-next;while (n2) { //当n2指向空时链表节点已经遍历完成next指针修改完成n2-next n1;n1 n2;n2 n3;if (n3)//对n3判空防止对空指针解引用n3 n3-next;}return n1;//当循环结束时n1是原链表的尾节点反转后的首节点}
}
bool chkPalindrome(struct ListNode* A) {struct ListNode* mid middleNode(A); //求出中间节点struct ListNode* rmid reverseList(mid);//后半部反转后的中间节点while (rmid A)//节点逐个对比{if (rmid-val ! A-val)return false;rmid rmid-next;A A-next;}return true;;
}
