目录
前言
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?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/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;
head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));//创建两个头节点
head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur=pHead;
while(cur) //遍历原链表
{
if(cur->val < x) //小于x就尾插到链表1
{
tail1->next=cur;
tail1=tail1->next;
}
else //大于等于x就尾插到链表2
{
tail2->next=cur;
tail2=tail2->next;
}
cur=cur->next;
}
tail1->next=head2->next; //将两个链表合并
tail2->next=NULL;
struct ListNode* head=head1->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* curA=headA,*curB=headB;
int lenA=1,lenB=1;
while(curA->next)
{
curA=curA->next;
lenA++;
}
while(curB->next)
{
curB=curB->next;
lenB++;
}
if(curA!=curB) //如果遍历到最后两个链表的尾节点不是同一个节点就说明不相交。
{
return NULL;
}
int t= abs(lenA-lenB);//求出差距步 abs是求绝对值的函数
struct ListNode* longlist=headA, *shortlist=headB;
if(lenB>lenA) //这里先假设链表A长，如果不是链表A长就交换一下，简化代码
{
longlist=headB;
shortlist=headA;
}
while(t--) //长的链表走差距步
{
longlist=longlist->next;
}
while(longlist!=shortlist)//两链表同时遍历
{
longlist=longlist->next;
shortlist=shortlist->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;
fast=slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
return true;
}
}
return false;
}题解也是非常简单。对于带环链表，今天这道题目属于热身，下期我会专门出一期带环链表的题目。
文章来源：https://www.toymoban.com/news/detail-631483.html
总结
最后，感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力，不断探索和挑战，成为数据结构领域的行家里手！文章来源地址https://www.toymoban.com/news/detail-631483.html
到了这里，关于数据结构刷题训练——链表篇（二）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
