网站建设管理经验做法,建筑工程公司宣传册设计样本,建设银行江苏省行网站,河南免费网站建设公司各位友友们#xff0c;好久不见呀#xff01;又到了我们相遇的时候#xff0c;每次相遇都是一种缘分。但我更加希望我的文章可以帮助到大家。下面就来具体看看今天所要讲的题目。 文章目录 1.环形链表2.环形链表II 1.环形链表
题目描述:https://leetcode.cn/problems/link…各位友友们好久不见呀又到了我们相遇的时候每次相遇都是一种缘分。但我更加希望我的文章可以帮助到大家。下面就来具体看看今天所要讲的题目。 文章目录 1.环形链表2.环形链表II 1.环形链表
题目描述:https://leetcode.cn/problems/linked-list-cycle/description/
这道题目呢,现阶段使用C语言的最优方案就是使用快慢指针的方法。下面就让我给大家介绍如何使用快慢指针的方法来解决这道题目。 我们假设让快指针一次走两步慢指针一次走一步。下面我将用图来更直观描述此题的逻辑。
1.当fast指针准备进环时,slow指针才走了fast指针的一半。 2.当slow指针准备进环时fast指针已经在环内转了几圈了。 3.当slow指针进环时fast指针就开始追击slow指针
走到这里这道题目实际上就变成了追击问题。当fast指针追上slow指针时说明该链表是带环链表。反之则为不带环链表。
思路清晰下面请看代码实现
bool hasCycle(struct ListNode *head) {struct ListNode* fast head,*slow head;while(fast fast - next){fast fast - next -next;slow slow -next;if(slow fast){return true;}}return false;
}其实这道题目还有两个问题 1为什么两个指针一定会相遇有没有可能会错过或者永远追不上 2当slow走一步时可不可以让fast指针一次走3步或者其它的步数呢
下面就根据以上两个问题分别讨论一下
1.我们假设slow进环时slow跟fast的距离为N 当fast开始追击slow的时候它们之间的距离变成N-1、N-2…直到0。说明它们每追击一次它们之间的距离就缩小1而距离为0时则它们相遇。
2.我们假设分析一下slow指针一次走一步fast指针一步走三步的情况
1当slow走了三分之一时fast指针已经准备开始进环了。 2.当slow指针走了三分之二时fast指针已经在环内转了几圈了。 3.当slow指针准备进环时fast指针又在环内转了不知道多少圈 我们还是假设slow指针进环时,fast指针和slow指针的距离为N 当fast指针开始追击slow指针时,它们的距离变化为:N-2、N-4、… 到这里就有两种情况产生 ①当N为偶数时:则最终的距离会变成0,则说明他们相遇 ②当N为奇数时:则最终的距离会变成-1,则说明它们错过了,进入新一轮的追击。 我们假设C代表环的长度那么新一轮追击的距离就变成C-1了。 这里又有两种情况 1)当C-1为偶数时:则来到第①这种情况,最后会追上。 2)当C-1为奇数时:则来到第②这种情况,它们将永远错过,无法相遇,陷入死循环。
那么当C为偶数N为奇数时则说明它们无法相遇是否会有这种情况发生呢 我们假设当slow指针准备进入环时slow指针走过的距离为Lfast指针走过的距离为L xC C-N。因此我们会产生一条等式 3L L xC C - N 化简就变为: 2L (x1)*C - N 偶数 (x1) × 偶数 - 奇数 ? 这显然等式不成立,则说明不可能存在C为偶数,N为奇数的这种情况,即不存在追不上的这种情况。
讨论完fast指针走三步的情况,那么fast指针走n步的情况也跟以上的方法类似,只不讨论的过程会更加繁琐一点。
2.环形链表II
题目描述:https://leetcode.cn/problems/linked-list-cycle-ii/description/ 这一道题目的解法也是用快慢指针这一方法。 想要找到入口点最简单的办法就是让一个指针从头开始走一个指针从fast指针和slow指针相遇的位置开始走当两个指针相遇时则找到入口点。 代码展示
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast head,*slow head;while(fast fast-next){fast fast - next - next;slow slow - next;//如果相遇了if(slow fast){struct ListNode* meet slow;while(meet ! head){meet meet - next;head head - next;}return meet;}}return NULL;
}现在又有一个问题为什么入口点就在那个地方呢下面就对其进行证明 假设从头开始走到入口点的距离为Lslow进环走的距离为N环形链表的长度为C 那么当fast指针和slow指针相遇时 fast指针走过的路程为: L xC N (x1的整数) slow指针走过的路程为: L N 因此我们得到一条等式: 2(L N) L xC N (x1) 化简得: L x*C - N,便于观察,我们可以将等式变为 L (x-1)*C C - N 因此,不管x的值为多少,只需让相遇点多走C - N的距离,就能说明head指针和meet指针相遇,从而找到入口点。
今天的分享就到这里啦如果感觉内容不错记得一键三连噢。创作不易感谢大家的支持我们下次再见ヾ(▽)ByeBye
