环形链表Ⅱ题目分析

环形链表Ⅱ是力扣上的一道在基于环形链表的题目的修改，不仅要判断是否为环形链表，其次还要返回链表开始入环的第一个结点。无环则返回空指针。

142. 环形链表 II - 力扣（LeetCode）

 先来判断是否有环

首先在思路上我们要明确：环形链表是不能遍历的，因为如果对环形链表进行遍历，就会导致死循环的问题，所以这里引入一个快慢指针的解决方案。

设置两个指针，分别为fast和slow，fast指针一次走两步，slow指针一次走一步。

在两个指针移动的过程中二者一定会在环中相遇，但是相遇的位置是不确定的。代码如下：

bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //判断fast->next是否为空是因为fast一次移动两个位置
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

简单的一个判断是否为环形链表的代码就完成了，判断还是很简单的，那么思考一个问题：

为什么快指针每次走两步，慢指针走一步就可以追上？

假设slow进环以后，fast和slow的距离是N，这是fast才真正开始追击slow，这个时候fast一次走两步，slow一次走一步，他们之间的距离缩小一。当距离缩小为0的时候，就追上了。

如何找环的入口点

先说解决方法：一个指针从head处开始走，另外一个指针从meet处开始走，二者最终会在入口点相遇。

那是如何推导的呢？

假设环的大小是C，假设head结点到入口点的距离为L，入口结点到meet结点的距离为X，slow指针从head开始走，走的路程为L+X，fast指针走的路程为L+nC+X（n>=1）；

之后就可以列出一个等式：2*（L+X）=L+n*C+X，化简后L=n*C-X 

得到的结论就是：一个指针从meet处开始走，另一个指针从head处开始走，最终它们会在入口点处相遇。

​
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* node = NULL;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            node = slow;
            break;
        }
    }
    if (node != slow)
        return NULL;
    fast = head;
    while (fast != node)
    {
        fast = fast->next;
        node = node->next;
    }
    return node;
}