检查链表是否连接回开始

Question

我试着检查一个链表的最后一个节点是否指向头部。这段代码似乎为问题给出了肯定的结果，但也为包含指向非头节点的节点的列表给出了假肯定。

我尝试了不同的方法，比如检查慢节点是否等于返回true点的head，但这似乎不起作用。

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

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

如果在slow到达头部之前发现了一个周期，那么我们发现了一个不同的周期。如果慢速使它与头一致，那么循环就是头一致。