天津市建设工程合同备案网站,如何进行网络销售,网站建设网站规划书,推广平台排行榜有哪些#x1f525;博客主页#xff1a;小王又困了
#x1f4da;系列专栏#xff1a;数据结构
#x1f31f;人之为学#xff0c;不日近则日退
❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 目录
一、链表分割
#x1f4a1;方法一#xff1a;
二、链表的回文
#x… 博客主页小王又困了
系列专栏数据结构
人之为学不日近则日退
❤️感谢大家点赞收藏⭐评论✍️ 目录
一、链表分割
方法一
二、链表的回文
方法一
三、相交链表
方法一
四、环形链表 方法一 ️前言 在上一期中我们给大家介绍了单链表也了解了单链表的实现。接下来就让我们进入实践练习一些经典题目让我们对单链表的理解更加深入 一、链表分割
题目 方法一 我们创建两条链表把小于x的节点放在一条链表中剩余的放在另一条节点最后将两条链表连接起来。在这里要使用带哨兵位的链表不用考虑头插和第一条链表为空的问题可以大大减少代码量。 注意要将链表最后一个节点的指针域置为空不然会导致链表循环。 ListNode* partition(ListNode* pHead, int x)
{struct ListNode* lhead ,*ltail,*ghead,*gtail;gheadgtail(struct ListNode*)malloc(sizeof(struct ListNode));lheadltail(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curpHead;while(cur){if(cur-valx){ltail-nextcur;ltailltail-next;}else {gtail-nextcur;gtailgtail-next;}curcur-next}ltail-nextghead-next;gtail-nextNULL;struct ListNode* headlhead-next;free(ghead);free(lhead);return head;
} 二、链表的回文
题目 方法一 我们先找到中间节点然后将后面的节点反转分别从头节点和中间节点开始比较如果两两节点的数据域有一对不相等返回flase如果都相等返回true。 class PalindromeList {public://找中间节点struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast head;struct ListNode* slow head;while (fast fast-next) {fast fast-next-next;slow slow-next;}return slow;}//反转链表struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* newnode NULL;while (cur) {//保存节点struct ListNode* next cur-next;//头插cur-next newnode;newnode cur;cur next;}return newnode;}bool chkPalindrome(ListNode* head) { struct ListNode* midmiddleNode(head);struct ListNode* rmidreverseList(mid);struct ListNode* curhead;while(rmidcur){if(rmid-val!cur-val){return false;}else {rmidrmid-next;curcur-next;}}return true;}
}; 三、相交链表
题目 方法一 在做这道题我们可以分为两步 1.判断是否相交 遍历两条链表比较最后一个节点的地址地址相等说明两条链表相交。 2.找起始节点 先计算出两条链表的长度计算出它们的差值让长的链表先走差距步然后两条链表一起走相等时返回的就是相交的起始节点。 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curAheadA,*curBheadB;int lenA1,lenB1;while(curA-next){curAcurA-next;lenA;}while(curB-next){curBcurB-next;lenB;}if(curA-next!curB-next){return NULL;}//求两链表的差距int gapabs(lenA-lenB);struct ListNode* longlistheadA,*shortlistheadB;if(lenAlenB){longlistheadB;shortlistheadA;}//长链表先走差距步while(gap--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
} 四、环形链表
题目 方法一 当我们定义快慢指针快指针一次走两步慢指针一次走一步。如果链表存在环在进入环中快指针一定可以追上慢指针。因为每走一步距离就减1当减到0时就追上了。 假设起点到入口点距离为L假设环的周长为C假设入口点到相遇点的距离为X 我们通过快慢指针走过的路程来判断但在这里要注意环的周长很小时所以在这里要考虑两种情况 情况一slow进环后一圈之内fast一定追上slow slow走的距离LXfast走的距离LCX 情况二slow进环时fast已经走了n圈 slow走的距离LXfast走的距离LnCX 由于快指针速度使慢指针的二倍所以快指针走的路程也是慢指针的二倍。由此可得出 结论慢指针从起点开始走快指针从相遇点开始走它们最终会相遇在入口点。 struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow,* fast;slowfasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){struct ListNode* meetfast;while(head!meet){meetmeet-next;headhead-next;}return meet;}}return NULL;
} 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位读者三连支持。文章有问题可以在评论区留言博主一定认真认真修改以后写出更好的文章。你们的支持就是博主最大的动力。
