环形链表2-找入环点

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

链接：142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路：

• 根据环形链表1：快慢指针

  fast一次走两步，slow一次走一步,如果存在环，fast和slow一定会相遇

• 如何找入环点

  结论：

  第一步：fast一次走两步，slow一次走一步。找到相遇点记为meetnode

  第二步：一个指针head从链表的头开始走，meetnode也在环内不断走，二者都是一次走一步。

  当head和meetnode相遇时：此时就是入环点

证明过程：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head)
 {
    //定义快慢指针
    struct ListNode* slow = head, *fast = head;
    //如果写成这样：struct ListNode* slow = head, fast = head;        fast是结构体变量，不是指针
    
    //不可以写成：fast->next && fast  
    //写成这样，当无环，且为偶数个结点，fast最后走到NULL，进行判断，如果把fast->next放在前面，会对空指针解引用，出错
    //要把fast放前面!!!
    while(fast && fast ->next )
    {
        //fast一次走两步
        fast = fast->next ->next;
        //slow一次走一步
        slow = slow->next;
        //如果fast和slow相遇说明有环
        if(fast == slow)
        {
            //meet从相遇点开始走
            struct ListNode* meet = slow;
           //当head和meetnode相遇时：此时就是入环点
           while(meet != head)
           {
               //meet和head一起走
               meet  = meet ->next;
               head = head->next;
           }
             //当meet和head相遇时，此时就是入环点
               return meet;
        }
    }
    //无环 返回NULL
    return NULL;
}

\