美文网首页
033-判断是否为环链表

033-判断是否为环链表

作者: Woodlouse | 来源:发表于2020-06-11 21:21 被阅读0次

    描述

    在一个单链表中,判断是否存在环。

    分析

    设置两个指针p1p2遍历链表:

    1,p1初始化为链表头节点,p2初始化链表头节点的下一个节点;

    2,p1遍历链表的步长为1,p2遍历链表的步长为2

    判断条件:

    p1==p2,则有环;

    p1==null或者p2->next==null*则无环;

    实现

    // Linked List Cycle
    bool isLinkedListCycle(ListNode *head)
    {
        if (!head || !head->next){
            return false;
        }
        
        ListNode *pStep1 = head; // 每次走一步的指针
        ListNode *pStep2 = head->next; // 每次走两步的指针
        
        // 判断指针是否会相遇
        while (pStep1 && pStep2->next) {
            if (pStep2 == pStep1) {
                return true;
            }
            pStep1 = pStep1->next;
            pStep2 = pStep2->next->next;
        }
        
        return false;
    }
    

    时间复杂度为O(n),空间复杂度为O(1)

    相关文章

      网友评论

          本文标题:033-判断是否为环链表

          本文链接:https://www.haomeiwen.com/subject/mpmitktx.html