如何判断链表中是否存在环形的问题:有两种情况,第一种是本身就是环形的。第二种情况是6型的。
首先是判断链表是否有交集,相同的指针地址。
最好的判断策略是操场跑步类似,如果没有环形,那么跑的快的最后会到达终点(单跑道),有环形的话,跑的快的最终会追上慢的。
设置两个指针p1和p2,每次p1向前走一步,p2向前走两步,直到p2碰到NULL或者两个指针相等时结束循环。
如果两个指针相等,说明该链表存在环。
bool isLoop(ListNode* head){
ListNode* p1,p2;
p1=p2=head->next;
if(head==NULL ‖head->next==NULL)
return false;
do{
p1=p1->next;//走一步
p2=p2->next->next;//走两步
}(p2 && p2->next && p1 !=p2);
if(p1==p2){
return true;
}else{
return false;
}
}