will the Floyd's cycle detection algorithm, with the fast pointer having three steps jump work?

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

}

Will the Floyd’s algorithm for cycle detection work if the fast pointer has the three steps as jump instead of two? can the Floyd’s algorithm work if the fast pointers has steps jump are 3,4,5,7 ..etc?

You need to sign in to view this answers

Related Post