[算法练习FindLoop]判断单向链表是否存在循环/循环入口/环长度

aiai101

定义两个指针;
第一个指针向前跑,另一个指针跑第一个指针跑过的,如果发现相等,则说明存在循环
我的设计是用一个变量记录第一个指针跑过的个数 然后根据这个数决定第二个指针跑几次
如果发现相等就循环
代码：
//pEnd跑pFirst跑过的 如果pEnd在跑的过程中发现与pFirst相同的即为循环链表
int FindLoop(PNODE head)
{
        PNODE pFirst = 0;
        PNODE pEnd = pFirst = head;
        ULONG count = 0;
       
        while( pFirst != NULL && pEnd != NULL && pFirst->next != NULL )
        {
                pFirst = pFirst->next;
                pEnd = head;
                count ++;
               
                for(ULONG i=0;i<count;i++)
                {
                        if(pEnd == pFirst)
                        {
                                return 1;
                        }
                        pEnd = pEnd->next;
                }
        }
        return 0;

}[/code]
这个代码可以改为返回节点,得到循环点
也可以改改 第二个循环条件改为两个指针不相等
代码：
有一些改变,pf用来跑全程
NODE *FindLoop_Ex_Ex(NODE *head)
{
        NODE *pc = head;
        NODE *pf = NULL;

        if (!pc)
                return NULL;

        while (pc)
        {
                pf = head;

                while(pf && pf != pc)
                {
                        //当前结点的下一个结点是它前面的某个结点或者是它自己，则为循环处
                        if (pc->next == pf || pc->next == pc)
                                return pc->next;
                        pf = pf->next;
                }

                pc = pc->next;
        }

        return NULL;
}[/code]


如果不需要知道循环点的话，可以使用步长法：
原理：如何判断是否有环？如果有两个头结点指针，一个走的快，一个走的慢，那么若干步以后，快的指针总会超过慢的指针一圈。
int FindLoop_Ex(NODE *head)
{
        NODE *p = NULL;
        NODE *q = NULL;

        if (head == NULL)
                return 0;

        p = head;
        q = head->next;

        while (p != NULL && q != NULL && q->next != NULL && p != q) //p != 关键判断 等同入在下面代码中写入 if(p == q)
        {
                p = p->next;
                q = q->next->next;
        }

        if (p == q)
                return 1;
        else
                return 0;
}[/code]

如何计算环的长度？第一次相遇（超一圈）时开始计数，第二次相遇时停止计数。
根据步长法来得到

int GetLoopLen(PNODE head)
{
        NODE *p = NULL;
        NODE *q = NULL;
        int len = 0;
        bool ok = false;

        if (head == NULL)
                return 0;

        p = head;
        q = head->next;

        while (p != NULL && q != NULL && q->next != NULL)
        {
                p = p->next;
                q = q->next->next;

                if(p == q)
                {
                        if(ok)
                        {
                                ok = false;
                                break;
                        }
                        p = head;
                        q = head->next;
                        ok = true;
                }
                if(ok)
                        len++;
        }

        return len;

}[/code]