Floyd循环检测算法，快速指针具有三步跳转是否有效？

Question

类 SingleLinkedList { 链表节点头； // 无需创建对象即可创建实例

class Listnode { // classes and methods can be static or non-static
    int data;
    Listnode next;
    Listnode(int data) {
        this.data = data;
        this.next = null;
    }
}

}

类 SingleLinkedList1 扩展 SingleLinkedList {

// Remove duplicates from a sorted linked list
void delete_duplicate() {
    Listnode current = head;
    while (current != null && current.next != null) {
        if (current.data == current.next.data) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
}

// Insert a node in a sorted linked list
void insert_node_sorted_list(int x) {
    Listnode key = new Listnode(x);
    if (head == null || head.data >= key.data) {  // Handle empty list or head insertion
        key.next = head;
        head = key;
        return;
    }

    Listnode current = head;
    Listnode previous = null;
    while (current != null && current.data < key.data) {
        previous = current;
        current = current.next;
    }
    previous.next = key;
    key.next = current;
}

// Remove the first occurrence of a key from the list
void remove_key(int x) {
    Listnode current = head;
    Listnode previous = null;
    if (head != null && head.data == x) {
        head = head.next;
        return;
    }
    while (current != null && current.data != x) {
        previous = current;
        current = current.next;
    }
    if (current != null) {
        previous.next = current.next;
    }
}

// Detect a loop in the linked list using Floyd's Cycle Detection Algorithm
boolean detect_loop() {
    Listnode fast_ptr, slow_ptr;
    slow_ptr = fast_ptr = head;
    while (fast_ptr != null && fast_ptr.next != null) {
        fast_ptr = fast_ptr.next.next;
        slow_ptr = slow_ptr.next;
        if (slow_ptr == fast_ptr) {
            return true;
        }
    }
    return false;
}

// Find the starting node of a loop in the linked list
Listnode start_node_of_loop() {
    Listnode fast_ptr = head;
    Listnode slow_ptr = head;
    while (fast_ptr != null && fast_ptr.next != null) {
        fast_ptr = fast_ptr.next.next;
        slow_ptr = slow_ptr.next;
        if (fast_ptr == slow_ptr) {
            return get_the_starting_node(slow_ptr);
        }
    }
    return null;
}

// Helper function to find the starting node of a loop
Listnode get_the_starting_node(Listnode slow_ptr) {
    Listnode temp = head;
    while (slow_ptr != temp) {
        temp = temp.next;
        slow_ptr = slow_ptr.next;
    }
    return temp;
}

public static void main(String[] args) {
    SingleLinkedList1 sll = new SingleLinkedList1();
    sll.head = sll.new Listnode(1);
    Listnode second = sll.new Listnode(2);
    Listnode third = sll.new Listnode(3);
    Listnode fourth = sll.new Listnode(3);
    Listnode fifth = sll.new Listnode(5);
    Listnode sixth = sll.new Listnode(5); // 1-->2-->3-->3-->5-->5

    sll.head.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = fifth;
    fifth.next = sixth;
    sixth.next = third; // Creating a loop

    System.out.println(sll.detect_loop()); // Detect if there's a loop

    Listnode startNode = sll.start_node_of_loop();
    if (startNode != null) {
        System.out.println("Start of loop: " + startNode.data); // Print the start of the loop
    } else {
        System.out.println("No loop detected.");
    }
}

}

如果快速指针具有三步跳转而不是两步跳转，Floyd 循环检测算法是否有效？如果快速指针的跳跃步数是 3,4,5,7 ..etc，Floyd 算法可以工作吗？

Answer 1

想象一个时钟。乌龟（慢指针）从 12 开始。兔子（快指针）从 1 开始。乌龟每次走一小时。兔子一次走三个小时。会发生什么？

tortoise: 12,1,2, 3,4,5,6, 7,8,9,10,11,12,1,2, 3,4,5,6, 7,8,9,10,11,12
hare:      1,4,7,10,1,4,7,10,1,4, 7,10, 1,4,7,10,1,4,7,10...

他们永远不会落在同一个号码上。

因此，如果将野兔的步长更改为 3，则所编写的算法（每次迭代后检查两个指针是否位于同一位置）将不起作用。