商城网站设计教程,正常网站 月均ip pv,别人用我的备案信息做网站,网站建设的目的及功能定位是啥目录 前言
1.题目一#xff1a;链表分割
1.1 思路
1.2 分析 1.3 题解
2. 题目二#xff1a;相交链表
2.1 思路
2.2 分析
2.3 题解
3. 题目三#xff1a;环形链表
3.1 思路
3.2 分析
3.3 题解
总结 前言 本期继续分享链表相关的OJ题目#xff0c;在这个专栏博客…
目录 前言
1.题目一链表分割
1.1 思路
1.2 分析 1.3 题解
2. 题目二相交链表
2.1 思路
2.2 分析
2.3 题解
3. 题目三环形链表
3.1 思路
3.2 分析
3.3 题解
总结 前言 本期继续分享链表相关的OJ题目在这个专栏博客中我们将提供丰富的题目资源和解题思路帮助读者逐步提高解题能力。同时我们也将分享一些刷题技巧和经验帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践相信读者可以在数据结构领域取得长足的进步。 1.题目一链表分割
题目描述 题目链接
链表分割https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8tqId11004rp2ru/activity/ojqru/ta/cracking-the-coding-interview/question-ranking
1.1 思路 这道题目没有示例这也是这道题的难点之一我们只根据题意自己寻找示例进行分析。题目的意思是说给一个链表给一个x值把小于x的插入到x前边大于x的插入到x的后边且不可以打乱原链表中的次序链表中的数据大小为乱序。理解了题意大家可以先自己思考一下解题思路。 对于这道题的要求我们可以这样做遍历原链表将大于等于x的尾插到一个新链表小于x的尾插到一个新链表最后将两个链表合并。
1.2 分析 这道题思路虽然非常简单但是在实际编写代码时会有很多的坑。例如要考虑链表为NULL的情况如果原链表中的所有值都大于x或小于x那就会造成两个链表中其中一个链表为NULL。 假设原链表为 x值为3那我们就可以把原链表分割成以下两个链表 这道题目有两种方法一种是使用带头节点的链表一种是使用不带头节点的链表。对于链表掌握不熟悉的本人推荐使用带头节点的链表当然带头节点的链表对于这道题也可以简化代码。如果没有带头节点那我们在初始化后尾插时就需要进行特殊处理。相对比较麻烦所有我们这里推荐使用带头链表。 如果带头结点两链表就是这样的 将两个链表合并时也不需要特殊处理可以直接连接如下图 不用担心头节点怎么办两个头节点最后会被销毁销毁之后就是我们所需要的链表了。 就算是第一个链表为空也可以搞定 连接的时候也不需要特殊处理最后销毁两个头节点即可。 1.3 题解
根据分析的思路我们对代码进行编写
ListNode* partition(ListNode* pHead, int x) {struct ListNode* head1,*head2,*tail1,*tail2;head1tail1(struct ListNode*)malloc(sizeof(struct ListNode));//创建两个头节点head2tail2(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curpHead; while(cur) //遍历原链表{if(cur-val x) //小于x就尾插到链表1{tail1-nextcur;tail1tail1-next;}else //大于等于x就尾插到链表2{tail2-nextcur;tail2tail2-next;}curcur-next; }tail1-nexthead2-next; //将两个链表合并tail2-nextNULL;struct ListNode* headhead1-next;free(head1);free(head2);return head; //最后返回链表1的第一个节点}
2. 题目二相交链表
题目描述 示例 题目链接
相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
2.1 思路 这道题目的解题思路就简单了但要注意链表长度不同的情况。当两个节点的节点个数不相同时指向长链表的指针要先走它们节点个数的差值步。然后开始一一对比直到遇到相交节点为止。
2.2 分析 链表相交并不是像直线那样交叉相交单链表中一个节点只能指向一个节点所有这里的链表相交是如下图的情况 总体分 3 步
先遍历两个链表得到两个链表的长度。长的链表先走差距步len1-len2。开始遍历两个数组直到相交点返回相交的节点
2.3 题解
整理完思路后根据分析的思路进行编写代码
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!curB) //如果遍历到最后两个链表的尾节点不是同一个节点就说明不相交。{return NULL;}int t abs(lenA-lenB);//求出差距步 abs是求绝对值的函数struct ListNode* longlistheadA, *shortlistheadB;if(lenBlenA) //这里先假设链表A长如果不是链表A长就交换一下简化代码{longlistheadB;shortlistheadA;}while(t--) //长的链表走差距步{longlistlonglist-next;}while(longlist!shortlist)//两链表同时遍历{longlistlonglist-next;shortlistshortlist-next;}return longlist; //循环停止时指向的节点就是第一个相交节点返回它们两个任意一个
}
3. 题目三环形链表
题目描述 示例 题目链接
环形链表https://leetcode.cn/problems/linked-list-cycle/description/
3.1 思路 我们知道循环链表循环链表的尾指向链表的头遍历一遍之后会回到链表的头但这道题属于带环链表带环链表的尾不一定连接着头它可能连接着任意节点。带环链表的题目属于链表中较为复杂的题目那要如何判断一个链表是否带环呢 首先我们知道带环链表在向后遍历的时候一定会回到入环点比较链表中的节点是否为入环时的节点就可以了但是问题来了我们怎么知道哪个是开始入环的节点不知道入环的节点又怎么比较是否是同一个节点。显然传统的思路行不通那我们就来换一种方法。 这里我们就可以使用快慢指针的方法一个指针走的快一个指针走的慢当快的指针再次与慢指针相遇那就说明这个链表一定是带环链表。
3.2 分析 带环链表的入环节点可能是任意节点 它也可以指向它自己。 这里我们可以使用快慢指针的方法使用快指针来追击慢指针当快指针与慢指针再次相遇这就说明这个链表一定为带环链表但是如果快指针走到了NULL这就说明这个链表不是带环链表。
3.3 题解 根据分析的思路我们整理一下形成代码
bool hasCycle(struct ListNode *head) {struct ListNode* fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){return true;}}return false;
} 题解也是非常简单。对于带环链表今天这道题目属于热身下期我会专门出一期带环链表的题目。 总结 最后感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力不断探索和挑战成为数据结构领域的行家里手
