弗洛伊德的循环检测算法:说明如何在链表中找到循环的起始节点?☆☆☆
回答:
这是用于循环检测的弗洛伊德算法。一旦发现一个节点是周期的一部分,如何找到周期的起点?
- 在弗洛伊德算法的第一部分中,野兔为乌龟的每一步移动了两步。如果乌龟和野兔相遇过,那就有一个循环,并且相遇点是循环的一部分,但不一定是循环中的第一个节点。
- 乌龟和野兔相遇后,让我们将乌龟放回列表的开头,然后将野兔保持在它们相遇的位置(距离周期开始k步)。如果我们让他们以相同的速度(1步两种),将他们曾经再次见面将是周期开始时的第一次。
另一个要提到的解决方案是Hash Map:
- 遍历节点列表。
- 对于遇到的每个节点,将其添加到身份哈希映射中
- 如果该节点已存在于身份映射中,则该列表具有环形链接,并且知道此冲突之前的节点(在移动之前进行检查或保留“最后一个节点”)
实现方式:
JAVA
public ListNode getLoopStartingPoint(ListNode head) {
boolean isLoopExists = false;
ListNode slowPtr = head, fastPtr = head;
while (!Objects.isNull(fastPtr) && !Objects.isNull(fastPtr.getNext())) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext().getNext();
if (slowPtr == fastPtr) {
isLoopExists = true;
break;
}
}
if (!isLoopExists) return null;
slowPtr = head;
while (slowPtr != fastPtr) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext();
}
return slowPtr;
}
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 弗洛伊德的循环检测算法:说明如何在链表中找到循环的起始节点?☆☆☆
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 弗洛伊德的循环检测算法:说明如何在链表中找到循环的起始节点?☆☆☆
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。