1. 判断单链表是否有环
    采用网络上常用的追赶的方式，原理：若存在环，则在环内的两个对象在速度不同时一定会相遇，速度快与速度慢的对象分别记为A,B，为避免A的一步太大，将B忽略，故设A的一步为2，B的一步为1，保证在一步内A或者在B之后，或者与B相遇;若不存在环，A先跑至终点
    
设链表为N1,N2,...,Nn
fun IsLooped :
    stepSlow = stepFast = N1;
    
    if stepFast->next == null or stepFast->next->next == null:
        return no-looped;
    stepFast = stepFast->next->next;

    while stepSlow != stepFast and stepFast->next != null and stepFast->next->next != null:
        stepSlow = stepSlow->next;
        stepFast = stepFast->next->next;
    
    if stepSlow == stepFast: // 相遇
        return looped;
    else : // 速度快的对象至终点
        return no-looped;
end fun.

2. 若单链表存在环，则求环的长度    
    上面已经能够得到相遇的位置，从相遇位置出发，只需要其中一个对象再绕环走一圈，即可得到环的长度

设链表为N1,N2,...,Nn
fun LoopLength :
    stepSlow = stepFast = N1;
    len = 0;
    
    if stepFast->next == null or stepFast->next->next == null:
        return no-looped;
    stepFast = stepFast->next->next;

    while stepSlow != stepFast and stepFast->next != null and stepFast->next->next != null:
        stepSlow = stepSlow->next;
        stepFast = stepFast->next->next;
    
    if stepSlow == stepFast: // 相遇
        len = 1; // 相遇位置即是第一个点
        stepFast = stepFast->next;
        while stepSlow != stepFast: // 没有回到相遇点，则说明该点未被统计，长度加1
            ++len;
            stepFast = stepFast->next;
        return looped, len;
    else : // 速度快的对象至终点
        return no-looped;
end fun.

3. 若单链表存在环，则求环的入口点
    将循环部分与非循环部分分开，设起始非循环部分为N1,N2,...Nm，循环部分为M1,M2,...,Mn,则单链表即为N1,N2,...,Nm,M1,M2,...Nn,M1,M2,....，目的是求点M1位置，即得到m的值.
    分析: 从上面可知，能够得到相遇位置Mi和环的长度n，额外地，可知道速度慢的对象B走过的路程S(即相遇点前面的点的个数); 由于速度快的对象A先于B到达循环部分，故在B达到点M1时，A已在循环部分溜达了t圈，并且已经在点Ms的位置，根据A走过路程有方程：

　　　　m+tn+s = 2m     (1);

若Ms=M1,则已找到入口点，现在考虑一般情况,1<=s<=n,
    目前，对象A和B的位置分别为M1,Ms,由于A的速度是B的2倍，故A走完一圈，B仅走过半圈，故B与A第一次相遇时，B未到过Mn,故B走过的路程为

　　　　m+(i-1) = S      (2)，

A走过的路程为

　　　　m+tn+n+(i-1) = 2S      (3)
    现在有方程 m+tn+s = 2m =>
    　　　　m = tn + s , 0<=s<n (1)
    　　　　m + (i-1) = S (2)
    　　　　m + tn + n + (i-1) = 2S (3)
    方程(3)-(2):
    S = tn + n (4)，方程(1)代入(2)
    tn + s + (i-1) = S = tn + n =>
    s + (i-1) = n, => s = n - (i-1), 而Mi,Mi+1,...,Mn,M1走过的路程为n - (i-1),说明，若对象C，D分别位于Ntn+1(0<=tn<=m),Mi时，经过s步可在M1处相遇，即可得到入口。tn可由方程(4)得到

fun LoopEntry :
    stepSlow = stepFast = N1;
    len = 0;
    steps = 0;
    
    if stepFast->next == null or stepFast->next->next == null:
        return no-looped;
    stepFast = stepFast->next->next;

    while stepSlow != stepFast and stepFast->next != null and stepFast->next->next != null:
        stepSlow = stepSlow->next;
        stepFast = stepFast->next->next;
        ++steps;
    
    if stepSlow == stepFast: // 相遇
        len = 1; // 相遇位置即是第一个点
        stepFast = stepFast->next;
        while stepSlow != stepFast: // 没有回到相遇点，则说明该点未被统计，长度加1
            ++len;
            stepFast = stepFast->next;
    else : // 速度快的对象至终点
        return no-looped;
        
    // 环长度大于0，即存在环,下面一定是存在环的，因为不存在环的情况已经在上面返回了
    if len > 0 :
        tn = steps - len;
        i = 0;
        entryNode = N1;
        // entryNode移至Mtn+1位置
        while i < tn :
            entryNode = entryNode->next;
            ++i;
        // entryNode与Mi同时移动s步，与入口处相遇
        while entryNode != stepSlow :
            entryNode = entryNode->next;
            stepSlow = stepSlow->next;
        return looped, entryNode;
end fun.

单链表环问题