Floyd环检测算法：快指针步长为3及更大值时是否可行？

问题描述 #

请问当Floyd环检测算法中的快指针每次跳3步而非2步时，该算法是否仍能正常工作？此外，快指针步长设为3、4、5、7等更大数值时，算法是否依然有效？

原算法代码（Java实现） #

class SingleLinkedList {
    Listnode head; // instance creation is possible without creation of the object

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

class SingleLinkedList1 extends 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.");
        }
    }
}

问题解答 #

1. 快指针步长为3时，算法是否有效？ #

仍然可以检测到环，但需要调整终止条件和逻辑细节：

• 核心逻辑：当快慢指针都进入环后，快指针每次比慢指针多走2步（步长3-步长1）。不管环的长度是多少，只要快指针不会越界访问空节点，两者最终一定会相遇——因为快指针相对于慢指针的速度恒定，环内的相对距离会不断缩小，直到重叠。
• 注意事项：原算法的终止条件fast_ptr != null && fast_ptr.next != null需要修改，要确保fast_ptr.next和fast_ptr.next.next都不为null，否则会触发空指针异常。

2. 快指针步长设为3、4、5、7等更大数值时，算法是否依然有效？ #

只要满足两个条件，算法依然可以有效检测环：

• 快指针步长k大于慢指针步长（通常慢指针步长为1）；
• 循环中要严格判断快指针能连续跳k步而不访问空节点（比如步长为k时，需要确保fast_ptr、fast_ptr.next……直到fast_ptr.next^(k-1)都不为null）。

从数学角度看，当快慢指针进入环后，快指针相对于慢指针的速度是(k-1)步每轮。设环长为L，初始相对距离为d，经过t轮后，相对距离变为(d - t*(k-1)) mod L，总会存在t使得该值为0，即两者相遇。

但要注意两个关键点：

• 步长越大，可能需要更多轮次才能相遇，极端环长下相遇时间会更长；
• 原算法中寻找环起点的逻辑（相遇后将慢指针移到表头，两者同速前进）只适用于快指针步长为2、慢指针步长为1的情况。如果快指针步长更大，这个逻辑不再成立，需要重新推导数学公式来定位环起点。

内容的提问来源于stack exchange，提问作者AMITESH