环形链表找环路入口的方法和证明_环形链表的入口

1.环形链表如何判断有环

环形链表就是存在环路的链表。也就是如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环（如下图）。所以我们就可以看看一个节点是否会再次被访问到，判断有无环路，给出下面两种方法。

1.1利用哈希表来判断

我们知道哈希表可以用来储存一对映射关系，我们可以把每个节点和它出现的次数存到哈希表中，我们再查表来判断，这个节点是否出现了两次，如果出现了两次，这样就说明存在环。
下面是代码：

bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) 
        {
            //如果这个点哈希表存在过，则有环
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
       //到空都么有，说明无环
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个方法的空间复杂度时O(N)，时间复杂度是哈希表插入的次数，哈希表最坏插入节点个数次，所以时间复杂度为O(N)。

1.2快慢指针法

这个方法比较常用，空间复杂度为O(1)。
方法：定义两个快慢指针，快的一下走两个节点，慢的一个一下走一个节点，最后就是快的指针走的路程是慢的指针的两倍，如果存在环一定会相遇。如果没环，快指针会走到到空。

证明：没有环的时候这个是很明显正确的，我们现在来看看有环的情况。看下面这个图
我们可以看看慢指针刚进环的情况：现在快指针fast想要追上慢指针slow，只要走C-x的距离,(C为环的周长），又有快指针fast每次比慢指针slow多走一步，可以知道再走C-x次就一定可以追上。
下面是代码：

 bool hasCycle(ListNode* head) {
         
        if (head == nullptr || head->next == nullptr) 
            return false;
            
        ListNode* slow = head;
        ListNode* fast = head->next;

        while (slow != fast) {
             //判断走到空没
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.如何来找的环的入口

我们知道了如何判断有无环路，现在来看看如何找环路的入口，下面给出两种方法。

2.1公式法来求环的入口

看下面的推导：

这里推出快慢指针的相遇后的路程差为L，通过观察C-X恰好等于meetNode到入口的距离，如果我们让fast重新回到head，slow从meetNode走，那我们发现下次相遇的位置不就是slow走了L距离的位置，也就是入口。

这样我们得出方法： 先找到相遇点，再让快指针从head走，慢指针从相遇点走，再次相遇就是入口啦。

下面是代码：

ListNode *detectCycle(ListNode *head) 
{
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) 
        {
            slow = slow->next;
            if (fast->next == nullptr) 
            {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.2 转化为相交链表

断开环路转化为相交链表求交点问题，下面是代码：
这种方法步骤比较麻烦，但是好想，代码逻辑也不复杂。

 ListNode *detectCycle(ListNode *head) 
    {
        ListNode* fast=head;
        ListNode*slow=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;

            if(slow==fast)
            {
                //定义交叉链表的尾部
                ListNode*tail=fast;
                //找到第二个链表的头部，断开环路。
                ListNode*phead=fast->next;
                fast->next=NULL;

                //交叉链表的找交点
                int i=0,j=0;
                ListNode*t1=head;
                ListNode*t2=phead;

                while(t1!=tail)
                {
                    t1=t1->next;
                    i++;
                }
                while(t2!=tail)
                {
                    t2=t2->next;
                    j++;
                }

                t1=head;
                t2=phead;

                //让两个链表从相同长度开始遍历
                if(i>j)
                {
                    for(int h=0;h<i-j;h++)
                        t1=t1->next;
                }
                else
                {
                    for(int h=0;h<j-i;h++)
                        t2=t2->next;
                }

                //同时向后遍历招到交点，并恢复环路
                while(t1!=t2)
                {
                    t1=t1->next;
                    t2=t2->next;
                }

                tail->next=phead;
                return t1;
            }
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

下面是环状链表的题和相交链表的题，可以巩固一下
相交链表
环状链表
环状链表

3.为啥快指针一次走两次，而不能是三次，四次或五次呢？

最后这里进行一个补充证明，大家可以了解思考一下，是为什么？
这里我们拿一次走三下来举例，一次走四次或五次不行的原因也是一样的，下面是说明：

快指针fast一次走3次，则每次快慢指针的距离就缩短2，如果N是偶数，那走N/2次就可以相遇。如果不是偶数次呢，那fast会走到slow前面去，距离就变成了C-1(C为环的周长）。如果C-1是偶数，没事可以追上，如果是奇数呢，那就又进入了上次的情况，就陷入了循环，将永远追不上了。

一次走四步或五步，就要判断相关的长度与3或4的倍数关系了。但是我们一次走两步，N是一定可以被1整除的，一定是不会出现错过的情况的。