C语言 [力扣]详解环形链表和环形链表II

夜晚中的人海 2024-06-11 12:05:02 阅读 90

各位友友们,好久不见呀!又到了我们相遇的时候,每次相遇都是一种缘分。但我更加希望我的文章可以帮助到大家。下面就来具体看看今天所要讲的题目。

文章目录

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指针走过的距离为L,fast指针走过的距离为L + xC + C-N。因此,我们会产生一条等式:

3L = L + xC + C - N 化简就变为: 2L = (x+1)*C - N

偶数 = (x+1) × 偶数 - 奇数 ? 这显然等式不成立,则说明不可能存在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;}

现在又有一个问题:为什么入口点就在那个地方呢?下面就对其进行证明:

在这里插入图片描述

假设从头开始走到入口点的距离为L,slow进环走的距离为N,环形链表的长度为C

那么当fast指针和slow指针相遇时:

fast指针走过的路程为: L + xC +N (x>=1的整数)

slow指针走过的路程为: L + N

因此我们得到一条等式: 2(L + N) = L + xC +N (x>=1)

化简得: L = x*C - N,便于观察,我们可以将等式变为 L = (x-1)*C + C - N

因此,不管x的值为多少,只需让相遇点多走C - N的距离,就能说明head指针和meet指针相遇,从而找到入口点。

今天的分享就到这里啦,如果感觉内容不错,记得一键三连噢。创作不易,感谢大家的支持,我们下次再见!ヾ( ̄▽ ̄)ByeBye



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。