[数据结构与算法]环形链表判断

typedef struct Node
{
    int data;
    struct Node *next;
} STNode;

// 检查给出的链表是否为环形链表, p1步长为1，p2步长为2，若p1==p2则说明为环形(追急问题)
int IsCicleList(STNode *root)
{
    STNode *p1 = root;
    STNode *p2 = root;
    while (p1 != NULL && p2->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2)
        {
            return 1; // 环形
        }
    }
    return 0; // 非环形
}

// 获取环长度
int GetCicleLength(STNode *root)
{
    STNode *p1 = root;
    STNode *p2 = root;
    int meetCount = 0; // 相遇次数
    int cicleLength = 0; // 环长
    while (p1 != NULL && p2->next != NULL)
    {
        if (meetCount == 1)
        {
            // 第一次相遇到第二次相遇，p2比p2多多走一圈(步差*行走步数)
            cicleLength++;
        }
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2)
        {
            meetCount++;
            if (meetCount == 2)
            {
                break;
            }
        }
    }
    return cicleLength;
}