【数据结构与算法】求带环链表的入环节点(图文详解)
【摘要】 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
目录
一、问题描述
二、解题思路
方法一:数学公式推导法
预备知识
此方法的数学推导建立在判断链表是否带环的基础算法上,推荐阅读前置文章
点击下方文字
如图,通过快慢指针法得到两个指针相遇位置时
假设:
- 链表入环前的长度为L
- 环的长度为C
- 快慢指针相遇节点为meet
- 环的入口与相遇节点meet的距离为N
- 相遇时,快指针已经在环内走了X圈(X>=1,快指针至少比慢指针都走一圈才能追上)
推导过程:
在meet相遇点
慢指针移动距离为L+N
快指针移动距离为L+X*C+N
另外,快指针移动距离是快指针的两倍
快指针也可以写成2(L+N)
将两条公式结合起来
2(L+N)=L+X*C+N
化简
L+N=X*C
L=X*C-N
L=(X-1)*C+C-N
最终得到的公式:
L=(X-1)*C+C-N
该公式在图中说明的问题:
链表入环前的长度L
与相遇点到环入口的距离再加(X-1)圈 ——X最少为1,所以X-1至少为0
是相等的
结论:
如果两个指针分别从链表起始位置和相遇点meet开始移动,那么两个指针第一次相遇的节点就是环的入口
方法二:转换为相交链表问题求解
该方法是将带环链表问题转换为相交链表问题,将问题降级处理
首先,依然要 求得快慢指针相遇交点
然后将取得该节点下一个节点地址,令其成为一个单独链表的首节点,断开链表
之后,这个问题就可以转换为相交链表问题来解决
三、代码实现
方法一实现代码
struct ListNode {
int val;
struct ListNode* next;
};
typedef struct ListNode ListNode;
//方法一:数学推理法
struct ListNode* detectCycle1(struct ListNode* head)
{
ListNode* slow, * fast;
slow = fast = head;
ListNode* meet = NULL;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)//先求得快慢指针相遇节点
{
meet = slow;
while (meet != head)//两指针同时移动,相遇即是入口
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
方法二实现代码
//求相交链表的交点的函数
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
ListNode* pcurA = headA;
ListNode* pcurB = headB;
int countA = 0;
int countB = 0;
while (pcurA)//求出链表长度
{
pcurA = pcurA->next;
countA++;
}
while (pcurB)
{
pcurB = pcurB->next;
countB++;
}
int tmp = abs(countA - countB);//长度差值
ListNode* slow, * fast;
if (countA < countB)
{
slow = headA;
fast = headB;
}
else
{
slow = headB;
fast = headA;
}
while (tmp--)//长链表先走差值的步数
{
fast = fast->next;
}
while (fast && slow)//同步比较
{
if (fast == slow)
return fast;
fast = fast->next;
slow = slow->next;
}
return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{
ListNode* slow, * fast;
slow = fast = head;
ListNode* meet = NULL;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)//先求得快慢指针相遇节点
{
meet = slow;
ListNode* newhead = meet->next;
meet->next = NULL;//将环断开,变成两个相交的链表
return getIntersectionNode(head, newhead);
}
}
return NULL;
}
总结
两种方法可以自行选用
第一种方法属于推理复杂,代码简单第二种方法属于推理简单,代码实现细节复杂
可根据实际情况选择合适的方法
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)