前言
本期继续分享链表相关的OJ题目，在这个专栏博客中，我们将提供丰富的题目资源和解题思路，帮助读者逐步提高解题能力。同时，我们也将分享一些刷题技巧和经验，帮助读者更加高效地进行刷题训练。通过持之以恒的努力和不断的实践，相信读者可以在数据结构领域取得长足的进步。
1.题目一：链表分割
题目描述：
题目链接：
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. 题目二：相交链表
题目描述：
示例：
题目链接：
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. 题目三：环形链表
题目描述：
示例：
题目链接：
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; }
题解也是非常简单。对于带环链表，今天这道题目属于热身，下期我会专门出一期带环链表的题目。
总结
最后，感谢你的阅读和支持。希望你在这个数据结构的学习旅程中能够获得满满的收获和成就感。愿我们共同努力，不断探索和挑战，成为数据结构领域的行家里手！
