单链表之环及环起点

一、结点结构
        单链表的数据结构定义如下：
        typedef struct node
        {
            ElemType data;
            struct node *next;
        }list;
        其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、判断是否有环
        判断是否有环的原理是：利用两个指针，一个速度是另外一个的两倍，即慢指针每次移动一个节点，快指针每次移动两个节点，如果有环，则两指针会在某一个点相遇；如果无环，则快指针会先到达链表结尾。具体代码如下：
        bool hascircle(list *head)
        {
            if (NULL == head)
            {
                return false;
            }
            bool hascircle = false;
            list *slow=head, *fast=head;
            while (fast && fast->next)     // fast的下一个和下下一个结点不能为NULL，否则fast->next->next会异常
            {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast)         // 相遇了即fast追上slow了
                {
                    hascircle = true;
                    break;
                }
            }
            return hascircle;
        }

三、求环的起点
        求环的起点原理与求是否有环类似，但需要额外步骤：用两个步长分别为1和2的指针遍历链表，直到两者相遇，此时慢指针走过的长度就是环的长度，相遇后把其中一个指针（比如：步长为2的指针）重新设定为起始点，让两个指针都以步长1再走一遍链表，相遇点就是环的起始点。推理证明步骤如下：
        第一次相遇时：
                慢指针走过的路程：S1 = 非环部分长度 + 弧A长
                快指针走过的路程：S2 = 非环部分长度 + n*环长 + 弧A长
                由S1*2 = S2可以得出：非环部分长度 = n*环长 - 弧A长
        让指针A回到起始点后，走过一个非环部分长度，指针B走过了相等的长度，也就是n*环长，正好回到环的开头。
        如果不能理解这些的话，可以从纯数学的角度来看此问题，即非环部分长度 = n*环长 - 弧A长，那就行了，具体算法如下：
        list *beginofcircle(list *head)
        {
            if (NULL == head)
            {
                return NULL;
            }
            list *slow=head, *fast=head;
            while (fast && fast->next)                    // 找相遇点，但fast的下一个和下下一个结点不能为NULL，否则fast->next->next会异常
            {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast)                         // 相遇了即fast追上slow了
                {
                    break;
                }
            }
            if ((NULL == fast) || (NULL == fast->next))    // 此时链表无环
            {
                return NULL;
            }
            fast = head;                                   // fast指针移到链表起始点，slow保持在相遇点
            while (slow != fast)                           // fast和slow都以步长1开始移动
            {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;                                   // 再次相遇点即为环的起点
        }