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

环形链表的入口点

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

从表中我们会发现它们之间的距离就会缩小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