描述

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

分析

设置两个指针p1，p2遍历链表：

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)。