描述
在一个单链表中,判断是否存在环。
分析
设置两个指针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)。
网友评论