检查链表是否重新加入到开始

Question

我正在尝试检查链表的最后一个节点是否指向头部。此代码似乎给出了问题的正面结果，但也为包含指向非头节点的节点的列表提供了误报。

我一直在尝试不同的事情，例如检查慢速节点是否等于返回真点处的头部，但这似乎不起作用。

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;
}

有什么建议吗？

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;
}

好吧，第三次是一种魅力。

如果在慢速进入头部之前找到一个周期，那么我们发现了一个不同的周期。如果慢到头，那么循环就是头。

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？（以上实施）