当前位置：首页 > ds >正文

【LeetCode牛客数据结构】单链表的应用——环形链表及链表分割问题详解

ds 2025/9/5 0:53:00

🔥个人主页：胡萝卜3.0

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》、《数据结构》、《C++干货分享》、LeetCode&牛客代码强化刷题

⭐️人生格言：不试试怎么知道自己行不行

正文

一、环形链表1

1、题目描述

2、思路及代码

3、结论及证明

4、其他思路

二、环形链表2

1、题目描述

2、思路及代码

3、结论及证明

三、链表分割

1、题目描述

2、解题思路

3、思路转换成代码

前言：各位uu们，在刷题的时候，要多画图，画图有利于我们更快的思考出相应的解题思路！！！

正文

一、环形链表1

141. 环形链表 - 力扣（LeetCode）

1、题目描述

2、思路及代码

思路：设置两个指针，一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，比较来两个指针，如果相等，则说明有环；否则没有环。

将上面思路转换成代码：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

若有uu对循环条件不清楚的，可以看一下上面的链表的中间节点思路2。

3、结论及证明

思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！

因此，在带环链表中慢指针走一步，快指针走两步最终⼀定会相遇。

思考2：快指针⼀次走3步，走4步，...n步行吗?

所以，不管fast每次走几步，一定会相遇。

4、其他思路

我们也可以创建数组：

二、环形链表2

142. 环形链表 II - 力扣（LeetCode）

1、题目描述

示例

2、思路及代码

思路：首先判断链表是否有环（快慢指针），快慢指针找相遇点，相遇点到入环结点的距离==头结点到入环结点的距离。

将上面的思路转换成代码：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){//说明有环，快慢指针相遇//相遇点到入环结点的距离==头结点到入环节点的距离ListNode* pcur=head;while(pcur!=fast){pcur=pcur->next;fast=fast->next;}return fast;}}return false;
}

3、结论及证明

通过这题我们可以得出一个结论：

接下来，我们可以尝试证明一下这个结论

三、链表分割

链表分割_牛客题霸_牛客网

1、题目描述

2、解题思路

思路：创建两个新的头点，作为“哨兵位”，遍历原链表，比较结点中的值与x的大小，一个链表中放比x大的值，另一个链表放比x小的值，最后将这两个链表相连接，返回小的链表的头结点。

3、思路转换成代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
#include <random>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* lessHead,*lessTail;ListNode* greatHead,*greatTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));greatHead=greatTail=(ListNode*)malloc(sizeof(ListNode));//遍历链表，比较大小//大的放大链表中，小的放小链表中ListNode* pcur=pHead;while(pcur){if(pcur->val<x){lessTail->next=pcur;lessTail=lessTail->next;}else {greatTail->next=pcur;greatTail=greatTail->next;}pcur=pcur->next;}//链接两个链表lessTail->next=greatHead->next;greatTail->next=NULL;ListNode* ret=lessHead->next;free(lessHead);free(greatHead);lessHead=NULL;greatHead=NULL;return ret;}
};