[数据结构与算法]寒假必须学会的-环形链表找入环点问题

题目要求

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

思路：

• 根据环形链表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;
}