查找环链表的环入口

ListNode<int> * getLoopNode(ListNode<int> *head)
{
	auto fast=head;
	auto slow=head;
	while(1){
		if(fast==nullptr||slow==nullptr||fast->next==nullptr||slow->next==nullptr){
			return nullptr;
		}
		slow=slow->next;
		fast=fast->next->next;
		if(slow==fast){//相遇
			break;
		}
	}
	auto cur=head->next;
	auto cur2=slow;
	while(cur!=cur2){
		cur=cur->next;
		cur2=cur2->next;
	}
}

​ 设置快慢两个指针分别为fast和slow,初始时都指向链表头head. slow 每次走一步,
即slow=slow->next; fast每次走两步,即fast=fast->next->next.由于fast比slow
走得快,如果有环,fast 一定会先进入环,而slow后进入环。当两个指针都进入环后,经过
若F次操作后两个指针定能在环上相遇。这样就可以判断个链表是否 有环。
​ 如下图所示,当slow刚进入环时,fast 早已进入环。因为fast每次比slow多走一步
且fast与slow的距离小于环的长度,所以fast与slow相遇时,slow所走的距离不超过环
的长度。

image-20210811225416718

​ 如下图所示,设头结点到环的入口点的距离为a,环的入口点沿着环的方向到相遇点的距离
为x, 环长为r,相遇时fast绕过了n圈。

image-20210811225452938

​ 则有2(a+x)=a+nr+X,即a=nr-x。显然从头结点到环的入口点的距离等于n倍的环长减去
环的入口点到相遇点的距离。因此可设置两个指针,一个指向head, 一个指向相遇点,两个指
针同步移动(均为一次走一步), 相遇点即为环的入口点。

© 2021 hanbaoaaa record.浙ICP备20005263号
asdad
联系方式 asdasd
2021-5-8 4:19
sss
回复数 (0) 点击展开
加载更多

新增评论

称呼
联系方式
邮箱(选填)
内容

提交

取消