弗洛伊德的循环检测算法:说明如何在链表中找到循环的起始节点?☆☆☆

作者 : IT 大叔 本文共748个字,预计阅读时间需要2分钟 发布时间: 2020-10-13

回答:

这是用于循环检测的弗洛伊德算法。一旦发现一个节点是周期的一部分,如何找到周期的起点?

  • 在弗洛伊德算法的第一部分中,野兔为乌龟的每一步移动了两步。如果乌龟和野兔相遇过,那就有一个循环,并且相遇点是循环的一部分,但不一定是循环中的第一个节点。
  • 乌龟和野兔相遇后,让我们将乌龟放回列表的开头,然后将野兔保持在它们相遇的位置(距离周期开始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小站 » 弗洛伊德的循环检测算法:说明如何在链表中找到循环的起始节点?☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论