| 失效链接处理 |
|
美团面试题 PDF 下载
本站整理下载：
提取码：iwgd
相关截图：
主要内容：
给定一个单链表，只给出头指针h：
1、如何判断是否存在环？
2、如何知道环的长度？
3、如何找出环的连接点在哪里？
4、带环链表的长度是多少？
解法：
1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
2、对于问题2，记录下问题1的碰撞点p，slow、fast从该点开始，再次碰撞所走过的操作数就是环的长度s。
3、问题3：有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。(证明在后面附注)
4、问题3中已经求出连接点距离头指针的长度，加上问题2中求出的环的长度，二者之和就是带环单链表的长度
void Isloop(Llink head)
{
if(!head||!head->next)
return;
Llink p,q;
bool loop=false;
p=q=head->next;
while(q&&q->next)//判断是否有环
{
p=p->next;
q=q->next->next;
if(p==q)
{
loop=true;
break;
}
}
if(!loop)
cout<<"This link has not loop\n";
else
{
cout<<"This link has a loop\n";
Llink r=p;
q=head->next;
int nonloop=1,loopcount=1;
//nonloop计算非环结点数，loopcount计算环上结点数
do//计算环上的结点数
{
p=p->next;
++loopcount;
}while(p!=r);
--loopcount;
while(p!=q)//得到环的入口结点，同时计算得到非环的结点数
{
p=p->next;
q=q->next;
++nonloop;
}
--nonloop;
cout<<"\nStart of loop: "<<p->data<<endl;
cout<<"\nCount of nonloop: "<<nonloop
<<"\nCount of loop: "<<loopcount
<<"\nCount of Linknode: "<<nonloop+loopcount<<endl;
}
}
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
