博主ID:代码小豪
环形链表
先来看看环形链表的原题:
中间的部分叙述有点繁杂,简单来概括就是,假如有一个节点,如果一直调用该节点的next,最后会回到该节点,那么这个链表就是带环的。
环形链表的性质分析
假如有个cur指针从头开始遍历链表,如果这个链表不是环形链表,那么这个cur指针会遍历至NULL指针处
那么让一个指针从头开始遍历整个链表,如果这个指针到了NULL,就说明这个链表,不是环形链表。
while (cur)
{
cur = cur->next;
}
return false;
但是如果这个链表是环形链表该如何证明呢?因为环形链表中是不在空节点的(NULL)。如果cur一直遍历,那么迭代就会进入死循环
解决思路就是在环形链表当中加入一个标志指针,让这个指针处于环形处。
这样子让cur指针继续遍历链表,最后一定会遇上flag指针,证明这个链表是环形链表
快慢指针法
那么问题来了,如何让flag指针处于环内呢?因为如果计算机知道flag处于什么位置是环内,我又何必写一大堆代码证明这个链表是环形链表呢?而且如果这个链表不带环,那么flag又应该在什么位置呢?
为了解决这个问题,我们可以设置两个指针指向第一个节点,一个是快指针fast,一个是慢指针slow,让快指针一次递进多个节点,而慢指针依次递进一个节点,让这个操作进行循环。
如此操作,会发生两种情况
情况1,链表为非带环链表,fast指针来到空节点处(NULL),返回false
情况2,链表为带环链表,fast指针会一直循环遍历环形链表。slow一定会进入环内。
fast会在链表内循环遍历,所以fast有可能会和slow重合,如果fast和slow重合了,就说明这个链表是环形链表。
指针的追及相遇问题
通过前面前面分析可知,如果该链表是环形链表,那么快指针就有可能在环内与慢指针相遇,那么会不会发生快慢指针不会相遇的情况呢?
首先快指针一定是比慢指针移动更快的,我们假设快指针每次移动两个节点,慢指针每次移动一个节点。
我们假设现在有一个环形链表,这个链表的入口点为点P。
设慢指针来到入口p时,快指针与慢指针的距离为N
慢指针走一步,快指针会走两步,因此这两个指针的距离会随着执行次数,每次减一(慢指针的走1步,快指针的会走2步,那么快指针相距慢指针就近了一步)。
次数 | 距离 |
---|---|
0 | N |
1 | N-1 |
2 | N-2 |
依此类推 | |
N-2 | 2 |
N-1 | 1 |
N | 0 |
可以发现,如果快指针走两步,慢指针走一步,那么这两个指针一定会在环中相遇。
那么如果快指针一次移动三个节点,慢指针一次移动一个节点,我们能得出什么样的结论呢?
还是假设当慢指针到达入口点距离快指针的距离为N
当慢指针与快指针的距离N为偶数时
次数 距离 | |
---|---|
0 | N |
1 | N-2 |
2 | N-4 |
依次类推 | |
N/2-1 | 2 |
N/2 | 0 |
当N为偶数时,快慢指针会相遇
当快指针与慢指针之间的距离为奇数时
次数 距离 | |
---|---|
0 | N |
1 | N-2 |
2 | N-4 |
依次类推 | |
N/2-1 | 1 |
N/2 | -1 |
可以发现快指针会越过慢指针,此时快指针会比慢指针多一个节点左右的距离,快指针需要再次遍历整个环形链表,直到与慢指针相遇。
设环形链表的周长为C,那么此时快指针与慢指针的距离为C-1.
当C为奇数时,C-1为偶数
那么程序的运行次数与快慢指针的距离关系为
次数 距离 | |
---|---|
0 | C-1 |
1 | C-3 |
2 | C-5 |
依次类推 | |
(C-1)/2-1 | 2 |
(C-1)/2 | 0 |
由此推出,当N为奇数,C为奇数时,快指针最后会追上慢指针。
当C为偶数时,C-1为奇数
次数 距离 | |
---|---|
0 | C-1 |
1 | C-3 |
2 | C-5 |
依次类推 | |
(C-1)/2-1 | 1 |
(C-1)/2 | -1 |
可以发现快指针和慢指针的距离在这一次追及之后,快慢指针的距离又回到了C-1。所以当N为奇数,C为偶数(C-1为奇数)时,快指针走三个节点,慢指针走1个节点的方式会永远不会相遇。
综上所述,如果我们想用快慢指针相遇的方式证明环形链表,最好的方法是让快指针一次后进两个节点,而慢指针一次后进一个节点。
当快指针后进多个(大于等于2)的节点时,有可能会出现快慢指针永远无法相遇的情况。比如当快指针后进3个节点时,如果此时N为奇数,C为偶数时,快指针永远无法与慢指针相遇,从而导致死循环的出现
解题代码如下:
bool hasCycle(struct ListNode *head) {
if(head==NULL)
return false;
struct ListNode*slow=head;
struct ListNode*fast=head->next;
while(fast)
{
if(fast->next==NULL)
return false;
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}
环形链表(2)
这是前面环形链表的变形体,这个OJ的要求是这样的:假设这是一个环形链表,那么就要找到这个链表的入口节点,并将这个节点返回。如果是非环形链表,则返回NULL指针。
首先,我们将这个问题的实现分为两个部分,第一、我们要先确定这是一个环形链表,然后,我们求出这个环形链表的入口点。
确定环形链表的方法已经说明过了,现在要思考的是如何找到这个入口点。
我们首先来思考一下快慢指针的位移关系,已知,快指针的速度是慢指针的两倍,因此当慢指针来到入口点L时,快指针已经移动2L了。
我们假设从链表头到入口点的距离为L,从入口点到达相遇点的距离为N,环形链表的周长为C。
如果L>C。假如slow移动了L的距离来到入口点,可以知道fast移动距离为2L,在圈内循环了x圈(x至少为1)
当slow来到相遇点时,那么slow移动的距离是L+N,而fast移动的距离为L+N+(x+1)C。
如果L<C。假如slow移动了L的距离来到入口点,可以知道fast移动距离为2L,在圈内循环了0圈
当slow来到相遇点时,那么slow移动的距离是L+N,而fast移动的距离为L+N+C。
根据fast的位移是slow的两倍可以得出:
当L>C时,2(L+N)=L+N+(x+1)C。
当L<C时,2(L+N)=L+N+C。
可以合并成一个公式:
2(L+N)=L+N+yC。(y>=1).
合并同类项得L=yC-N。
我们可以图中明显的看出一个关系
如果一个指针从相遇点移动YC-N个节点时,会来到入口点。而且一个指针从链表头开始移动L位时,回来到入口点。
并且L=yC-N。
可以得出,如果让一个指针从链表头开始移动,一个指针从相遇点开始移动。这两个指针会在入口点相遇。文章来源:https://www.toymoban.com/news/detail-826832.html
代码如下:文章来源地址https://www.toymoban.com/news/detail-826832.html
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast)
{
if(fast->next==NULL)
return NULL;
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
struct ListNode*meet=slow;
while(meet!=head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return NULL;
}
到了这里,关于算法详解(力扣141——环形链表系列)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!