java - 检查链接列表是否重新加入以开始

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？（在上面实现）