首页 > 代码库 > 8.判断单链表是否有环(6形状)?如何找到环的“起始”点?如何知道环的长度?
8.判断单链表是否有环(6形状)?如何找到环的“起始”点?如何知道环的长度?
8.判断单链表是否有环(6形状)?如何找到环的“起始”点?如何知道环的长度?
思路:
注意分析题意,题意并非是说单链表完全成O形状的环,而是说单链表成6形状的环。
首先判断是否有环:为此我们建立两个指针,从Head一起向前跑,一个步长为1,一个步长为2,用
while(直到步长2的跑到结尾)
{
检查两个指针是否相等,直到找到为止。
}
来进行判断。
原因是,在这场跑步中,结束循环有两种可能,其一是原来无环,所以2先跑到结尾,因为2比1快,二者不可能相等。其二是原来是有环的,因为这场赛跑永远没有z终点,但是在环中,由于2比1快,因而必定套圈,也即2追上了1,这在无环中是不可能出现的情况。
而进行计算环的长度,只要找到交汇点,然后在圈中跑一次就可以了。
int getCircleLength(Node* cross)
bool judgeCircleExists(Node* Head)
//单链表成环,计算环的长度(输入的参数为成环的交汇点)int getCircleLength(Node* cross){ int len=1; Node* p=cross; while(p->next!=cross) //不能写作 p->next!=p { len++; p=p->next; } return len;}
//判断单链表是否有环,并且返回环的长度bool judgeCircleExists(Node* Head,int &len){ if(Head==NULL) //空链 return false; else if(Head->next==Head) //1个节点且成环 return true; else if(Head->next==NULL) //1个节点不成环 return false; //至少两个节点情形 //初始化跑步机 Node* p1=Head; //跑步者1号,跑到第1个节点 Node* p2=Head->next; //跑步者2号,跑到第2个节点 while(p2!=NULL&&p2->next!=NULL) //利用了&&短路 { p1=p1->next; p2=p2->next->next; if(p1==p2) { //此时p1(p2)即为交汇点 len=getCircleLength(p1); return true; } } return false;}
8.判断单链表是否有环(6形状)?如何找到环的“起始”点?如何知道环的长度?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。