【那些年那些题】循环链表

题目描述：

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

题目链接：环形链表 I

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

题目链接：环形链表 II

解题思路：

最容易想到的一个办法是暴力穷举，设置两个变量，然后进行逐一比较。但是这个想法是错误的，这种方法只适用于没有环的链表。如果有环就会出现死循环，然后程序跑崩。

 我们做一个假设，现在有一个有环链表，然后我们进行遍历。结果肯定是死循环的，但是我们思考一下过程，有环就说明这个链表的最后一个节点的next是指向前面某一个节点，也就是说循环是从整个节点开始，我们把这个节点叫做切入点。这里使用快慢指针的话，判断是否有环就变成追及问题了。只要快指针能追上慢指针，那就说明是有环的，如果快指针遇到空，就说明没有环。

 环形链表 I

 代码实现：

bool hasCycle(struct ListNode *head) {
    struct ListNode * fast = head, * slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            return true;
    }
    return false;
}

思考为什么快慢指针之间的速度差为1，如果是2、3这些会怎么样？

 如果速度差为1，每次循环N减小1…N最终会变成0，则成功。

 速度差为2，每次循环N减小2…最后两个结果0和-1，如果是0则成功了，但如果是-1这个时候就要重新开始追及。这个时候C的大小就很重要了，如果C是个奇数，则C-1-n*2，则在第二轮的时候追及成功;但是如果C是偶数，那就永远不可能追及成功了。

 环形链表 II

 代码实现：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head, * slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode* meet = slow;
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return false;
}