检查链表是否连接回起点

Question

我想检查链表的最后一个节点是否指向头节点。这段代码似乎可以解决这个问题，但是对于包含指向非头节点的节点的列表也会给出错误的结果。

我一直在尝试不同的方法，比如在返回true处检查慢节点是否等于头节点，但是似乎不起作用。

public boolean isLinkedToStart(Node head) {
    if (head == null) {
        return false;
    }
    Node fast = head.next;
    Node slow = head;
    while (fast != null && fast.next != null) {
        if (fast.next.next == slow) {
            return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

有什么建议吗？

- sff

---

这个算法（通常被称为“乌龟和兔子”算法）是一种通用的循环检测算法。它返回true，如果链表包含任何循环，不一定是指向头部的循环。你需要一个更具体的变体。 - Santa

头部是否以特定/可识别的方式定义？ - HC_

顺便说一句，好问题！这比我们想象的更具挑战性！ - Cruncher

你真的需要一个慢节点和快节点吗？为什么不只是遍历一次列表并检查是否有一个节点指向头部或一个节点指向null？请注意，慢-快算法是为了将复杂度从O(n^2)降低到O(n)。由于已知头部，因此这个问题已经可以在O(n)中解决。 - user1952500

@user1952500，请阅读我的评论，了解HC_答案中存在的问题。 - Cruncher

Answer 1

public boolean isLinkedToStart(Node head) {
    if (head == null) {
        return false;
    }
    Node fast = head.next;
    Node slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if(slow.next == head)
            return true;
        if (fast == slow)
            return false;
    }
    return false;
}

好的，第三次就是成功。

如果在慢指针到达头结点之前发现了一个循环，则我们找到了一个不同的循环。如果慢指针到达头结点，则该循环为头结点。

- Cruncher

---

你是第一个提到“弗洛伊德循环查找算法”的人。 - Kayaman

我猜如果他得到一个错误的正面结果，这将会无限循环。 - Cruncher

是的，我认为它应该只是一个龟兔算法，在结尾处添加一个条件门。 - Santa

@ChuckCottrill 如果需求变更，很容易进行编辑。只需将第一个 return false; 更改为任何其他值即可。也许是 -1、0、1？但在这个“具体”的问题中，OP 想要 false。 - Cruncher

那个编辑在链表节点数为偶数时有效，但由于某些原因在奇数节点时无效。 - sff

Answer 2

public boolean isLinkedToStart(Node head) {
    if (head == null) {
        return false;
    }
    Node probe = head.next;
    while (probe != null) {
        if (probe == head) {
            return true;
        }
        if(probe.seen) {
            return false;
        }

        probe.seen = true;
        probe = probe.next;
    }
    return false;
}

你能修改节点结构吗？也就是说，你能添加像 node.seen == false 这样的内容，并在循环时将其切换为打开状态，然后修改这段代码^ 以检查循环时是否为未见过的节点，并在遇到“已看到”的节点时返回false吗？（以上实现）

- HC_