当前位置:   article > 正文

链表一:寻找环形链表的入口点

环形链表的入口

环形链表的入口点

1.首先怎么判断链表是否有环

寻找环形链表入口点的第一步,要先判断该链表是否为环形链表,环形链表的尾指针指向的位置是不确定的,它可以在任何位置成环。
如下面这些图所示:
在这里插入图片描述
那么如何判断是否有环呢?我们可以采用双指针法,思路如下:
具体地,我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。初始时,快、慢指针在位置 head。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。
代码如下:

bool hasCycle(struct ListNode *head) 
{
    struct ListNode *slow=head;     //慢指针
    struct ListNode *fast=head;     //快指针

    //慢指针一次走一步,快指针一次走两步
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

对于以上代码我们难免会提出以下两个问题;

(1)为什么slow走一步,fast走两步,他们一定会在环里面相遇,会不会永远追不上?请证明!

答:
不会追不上。假设slow进环的时候,fast与slow的距离是N,紧接着追击的过程中(fast追slow)fast向前走两步,slow走一步,他们每次一走,它们之间的距离就会缩小1,由一开始相距N,到后面相距0。
![在这里插入图片描述](https://img-blog.csdnimg.cn/2021041323160443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzgxMjYwMw==,size_16,color_FFFFFF,t_70

进环后fast与slow的距离
N
N-1
N-2
2
1
0

从表中我们会发现它们之间的距离就会缩小1由一开始相距N,到后面相距为0。
不管进环时,它们相距的距离是偶数还是奇数。最终我们发现一定fast一定会追上slow。
例如下面这个例子:
假设环里面只有8个节点,此时如slow与fast的位置如左下图所示:
在这里插入图片描述
最终fast与slow会在相遇点相遇
在这里插入图片描述

(2)slow走一步,fast走3步?走4步?走x步行不行?为什么?请证明!

在这里插入图片描述
此时我们就可以发现要发生相遇与fast走的步数和环中的节点数有关。
我们设fast走X步,环中结点数为Y
在这里插入图片描述

2.找入环点

在这里插入图片描述
经过上图我们分析我们可以写出如下代码:

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow = head;     //慢指针
    struct ListNode* fast = head;     //快指针

    //慢指针一次走一步,快指针一次走两步
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            //相遇结点
            struct ListNode*meet=fast;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }

    return NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/604730
推荐阅读
相关标签
  

闽ICP备14008679号