环形链表判断

最后冰吻free

于 2021-12-04 22:24:48 发布

阅读量492

点赞数

分类专栏：数据结构文章标签：链表

本文链接：https://blog.csdn.net/CodeHouse/article/details/121722925

版权

数据结构专栏收录该内容

23 篇文章

订阅专栏

本文介绍了如何使用C++编程语言实现判断链表是否为环形链表的IsCicleList函数，并进一步探讨了GetCicleLength函数获取环形链表长度的方法。通过步进比较节点，揭示了环形链表的特征和求解步骤。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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;
}