凡客做网站,公司建设网站的服务费,网站 关键词 出现频率,lnmp lamp wordpress#x1f493; 博客主页#xff1a;倔强的石头的CSDN主页 #x1f4dd;Gitee主页#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注 目录
一、问题描述
二、解题思路
方法一#xff1a;数学公式推导法
方法… 博客主页倔强的石头的CSDN主页 Gitee主页倔强的石头的gitee主页 ⏩ 文章专栏《数据结构与算法 经典例题》C语言 期待您的关注 目录
一、问题描述
二、解题思路
方法一数学公式推导法
方法二转换为相交链表问题求解
三、代码实现
方法一实现代码
方法二实现代码 一、问题描述
原题链接 142. 环形链表 II - 力扣Le142. 环形链表 II - 力扣Le 二、解题思路 方法一数学公式推导法
预备知识 此方法的数学推导建立在判断链表是否带环的基础算法上推荐阅读前置文章 点击下方文字 【数据结构与算法 刷题系列】判断链表是否有环-CSDN博客 如图通过快慢指针法得到两个指针相遇位置时 假设 链表入环前的长度为L环的长度为C快慢指针相遇节点为meet环的入口与相遇节点meet的距离为N相遇时快指针已经在环内走了X圈X1快指针至少比慢指针都走一圈才能追上 推导过程 在meet相遇点 慢指针移动距离为LN 快指针移动距离为LX*CN 另外快指针移动距离是快指针的两倍 快指针也可以写成2LN 将两条公式结合起来 2LNLX*CN 化简 LNX*C LX*C-N LX-1*CC-N 最终得到的公式
LX-1*CC-N 该公式在图中说明的问题 链表入环前的长度L 与相遇点到环入口的距离再加X-1圈 ——X最少为1所以X-1至少为0 是相等的 结论 如果两个指针分别从链表起始位置和相遇点meet开始移动那么两个指针第一次相遇的节点就是环的入口 方法二转换为相交链表问题求解 此方法的数学推到建立在判断链表是否带环的基础算法上推荐阅读 【数据结构与算法 刷题系列】相交链表-CSDN博客 该方法是将带环链表问题转换为相交链表问题将问题降级处理 首先依然要 求得快慢指针相遇交点
然后将取得该节点下一个节点地址令其成为一个单独链表的首节点断开链表 之后这个问题就可以转换为相交链表问题来解决 三、代码实现
方法一实现代码
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;
}总结 两种方法可以自行选用 第一种方法属于推理复杂代码简单 第二种方法属于推理简单代码实现细节复杂 可根据实际情况选择合适的方法
