Flyod Cycle Detection

#include <bits/stdc++.h> // Common includes
using namespace std;     // Standard namespace

// Node Class: Defines structure of a linked list node
class Node {
public:
    int data;   // Data storage
    Node* next; // Pointer to next node

    // Node Constructor
    Node(int data) {
        this->data = data;
        this->next = NULL; // Initialize next as NULL
    }
};

// printList: Prints all elements in the list
void printList(Node* head) {
    if(head == NULL) {
        cout << "List is Empty!" << endl;
        return;
    }

    cout << "Singly List : ";
    while(head != NULL) {
        cout << head->data << " "; // Print data
        head = head->next;         // Move to next node
    }
    cout << endl;
}

// insertAtHead: Adds node to the beginning
void insertAtHead(Node* &head, int data) {
    Node *temp = new Node(data); // Create new node
    temp->next = head;           // New node points to old head
    head = temp;                 // Head updates to new node
}

// insertAtTail: Adds node to the end
void insertAtTail(Node* &tail, int data) {
    Node *temp = new Node(data); // Create new node
    tail->next = temp;           // Old tail points to new node
    tail = temp;                 // Tail updates to new node
}

// insertAtMiddle: Inserts node at a specific position
void insertAtMiddle(Node* &head, Node* &tail, int data, int pos) {
    if(pos == 1) { // Special case: insert at head
        insertAtHead(head, data);
        return;
    }

    Node *temp = head; // Traverse pointer
    while(temp != NULL && pos > 2) { // Find node BEFORE insertion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node *insertNode = new Node(data); // Create node to insert
    insertNode->next = temp->next;     // New node points to temp's next
    temp->next = insertNode;           // Temp points to new node

    if(insertNode->next == NULL) { // Update tail if inserted at end
        tail = insertNode;
    }
}

// deletePosition: Deletes node at a specific position
void deletePosition(Node* &head, int pos) {
    Node *temp = head; // Pointer for deletion/traversal
    if(pos == 1) {     // Special case: delete head
        head = head->next;
        delete temp;   // Free memory
        return;
    }

    while(temp!=NULL && pos > 2) { // Find node BEFORE deletion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || temp->next==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node* target = temp->next; // Node to be deleted
    temp->next = target->next; // Bypass target node
    delete target;             // Free memory
}

// deleteValue: Deletes first occurrence of a specific value
void deleteValue(Node* &head, int val) {
    Node* temp = head->next; // Current pointer
    Node* prev = head;       // Previous pointer

    if(head->data == val) { // Special case: delete head by value
        head = head->next;
        delete prev; // Free old head
        return;
    }

    // Traverse to find the value
    while(temp!=NULL) {
        if(temp->data == val) {
            val = INT_MIN; // Sentinel to mark value found
            break;
        }
        prev = temp;       // Move prev
        temp = temp->next; // Move temp
    }

    if(prev->next==NULL || val!=INT_MIN) { // Value not found
        cout << "Value Not Found!" << endl;
        return;
    }

    prev->next = temp->next; // Bypass target node
    delete temp;             // Free memory
}

// floydDetectLoop: Detects if a cycle (loop) is present using Floyd's Cycle-Finding Algorithm (Tortoise and Hare)
bool floydDetectLoop(Node* head) {
    if(head == NULL) { // Empty list has no loop
        return false;
    }

    Node* slow = head; // Slow pointer (moves 1 step at a time)
    Node* fast = head; // Fast pointer (moves 2 steps at a time)

    // Traverse the list with two pointers
    while(slow != NULL && fast != NULL) {
        fast = fast->next; // Fast moves 1 step
        slow = slow->next; // Slow moves 1 step

        if(fast != NULL) { // Check if fast is not NULL before moving it again
            fast = fast->next; // Fast moves another step
        }

        if(slow == fast) { // If pointers meet, a loop is detected
            return true;
        }
    }

    return false; // Fast pointer reached NULL, no loop found
}

// main: Program entry point, demonstrates operations
int main() {
    Node *head = new Node(1); // Create initial node
    Node *tail = head;        // Tail points to head initially

    // Build list: 1 -> 2 -> 4 -> 8 -> 16 -> 32
    for(int i=1; i<=5; i++) {
        insertAtTail(tail, pow(2,i));
    }
    printList(head); // Print original list

    // Uncomment the line below to create a cycle for testing:
    // tail->next = head->next->next->next; // Example: 32 points to 8 (creating a cycle)

    // Check if a cycle is present using Floyd's algorithm
    if(floydDetectLoop(head)) {
        cout << "Cycle is present!" << endl;
    } else {
        cout << "Cycle is not present!" << endl;
    }

    return 0; // Indicate success
}

#include <bits/stdc++.h> // Common includes
using namespace std;     // Standard namespace

// Node Class: Defines structure of a linked list node
class Node {
public:
    int data;   // Data storage
    Node* next; // Pointer to next node

    // Node Constructor
    Node(int data) {
        this->data = data;
        this->next = NULL; // Initialize next as NULL
    }
};

// printList: Prints all elements in the list
void printList(Node* head) {
    if(head == NULL) {
        cout << "List is Empty!" << endl;
        return;
    }

    cout << "Singly List : ";
    while(head != NULL) {
        cout << head->data << " "; // Print data
        head = head->next;         // Move to next node
    }
    cout << endl;
}

// insertAtHead: Adds node to the beginning
void insertAtHead(Node* &head, int data) {
    Node *temp = new Node(data); // Create new node
    temp->next = head;           // New node points to old head
    head = temp;                 // Head updates to new node
}

// insertAtTail: Adds node to the end
void insertAtTail(Node* &tail, int data) {
    Node *temp = new Node(data); // Create new node
    tail->next = temp;           // Old tail points to new node
    tail = temp;                 // Tail updates to new node
}

// insertAtMiddle: Inserts node at a specific position
void insertAtMiddle(Node* &head, Node* &tail, int data, int pos) {
    if(pos == 1) { // Special case: insert at head
        insertAtHead(head, data);
        return;
    }

    Node *temp = head; // Traverse pointer
    while(temp != NULL && pos > 2) { // Find node BEFORE insertion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node *insertNode = new Node(data); // Create node to insert
    insertNode->next = temp->next;     // New node points to temp's next
    temp->next = insertNode;           // Temp points to new node

    if(insertNode->next == NULL) { // Update tail if inserted at end
        tail = insertNode;
    }
}

// deletePosition: Deletes node at a specific position
void deletePosition(Node* &head, int pos) {
    Node *temp = head; // Pointer for deletion/traversal
    if(pos == 1) {     // Special case: delete head
        head = head->next;
        delete temp;   // Free memory
        return;
    }

    while(temp!=NULL && pos > 2) { // Find node BEFORE deletion point
        temp = temp->next;
        pos--;
    }

    if(temp==NULL || temp->next==NULL || pos<=0) { // Invalid position check
        cout << "Invalid Position!" << endl;
        return;
    }

    Node* target = temp->next; // Node to be deleted
    temp->next = target->next; // Bypass target node
    delete target;             // Free memory
}

// deleteValue: Deletes first occurrence of a specific value
void deleteValue(Node* &head, int val) {
    Node* temp = head->next; // Current pointer
    Node* prev = head;       // Previous pointer

    if(head->data == val) { // Special case: delete head by value
        head = head->next;
        delete prev; // Free old head
        return;
    }

    // Traverse to find the value
    while(temp!=NULL) {
        if(temp->data == val) {
            val = INT_MIN; // Sentinel to mark value found
            break;
        }
        prev = temp;       // Move prev
        temp = temp->next; // Move temp
    }

    if(prev->next==NULL || val!=INT_MIN) { // Value not found
        cout << "Value Not Found!" << endl;
        return;
    }

    prev->next = temp->next; // Bypass target node
    delete temp;             // Free memory
}

// floydDetectLoop: Detects if a cycle (loop) is present using Floyd's Cycle-Finding Algorithm (Tortoise and Hare)
bool floydDetectLoop(Node* head) {
    if(head == NULL) { // Empty list has no loop
        return false;
    }

    Node* slow = head; // Slow pointer (moves 1 step at a time)
    Node* fast = head; // Fast pointer (moves 2 steps at a time)

    // Traverse the list with two pointers
    while(slow != NULL && fast != NULL) {
        fast = fast->next; // Fast moves 1 step
        slow = slow->next; // Slow moves 1 step

        if(fast != NULL) { // Check if fast is not NULL before moving it again
            fast = fast->next; // Fast moves another step
        }

        if(slow == fast) { // If pointers meet, a loop is detected
            return true;
        }
    }

    return false; // Fast pointer reached NULL, no loop found
}

// main: Program entry point, demonstrates operations
int main() {
    Node *head = new Node(1); // Create initial node
    Node *tail = head;        // Tail points to head initially

    // Build list: 1 -> 2 -> 4 -> 8 -> 16 -> 32
    for(int i=1; i<=5; i++) {
        insertAtTail(tail, pow(2,i));
    }
    printList(head); // Print original list

    // Uncomment the line below to create a cycle for testing:
    // tail->next = head->next->next->next; // Example: 32 points to 8 (creating a cycle)

    // Check if a cycle is present using Floyd's algorithm
    if(floydDetectLoop(head)) {
        cout << "Cycle is present!" << endl;
    } else {
        cout << "Cycle is not present!" << endl;
    }

    return 0; // Indicate success
}

1. What is it?

A linear data structure where elements are stored in nodes.
Each node has:
- data (the actual value)
- next (a pointer to the next node).
The last node’s next pointer is NULL.
Accessed via a head pointer (first node) and sometimes a tail pointer (last node for efficiency).

2. Core `Node` Structure

class Node {
public:
    int data;   // The value
    Node* next; // Points to the next node
    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

Key: Node* next is crucial for linking.

3. Basic Operations (Quick Glance)

printList(Node* head):
- Purpose: Traverse and display all elements.
- How: Start at head, loop while (head != NULL), print head->data, then head = head->next;.
- Edge Case: If head == NULL, list is empty.
- Example: 1->2->3 prints “Singly List : 1 2 3”
insertAtHead(Node* &head, int data):
- Purpose: Add a new node at the beginning.
- How: 1. Create new node. 2. New node’s next points to old head. 3. head becomes new node.
- Key: head is passed by reference (&).
- Example: 2->3 + insertAtHead(head, 1) → 1->2->3
insertAtTail(Node* &tail, int data):
- Purpose: Add a new node at the end.
- How: 1. Create new node. 2. Old tail’s next points to new node. 3. tail becomes new node.
- Key: tail is passed by reference (&).
- Example: 1->2 + insertAtTail(tail, 3) → 1->2->3
insertAtMiddle(Node* &head, Node* &tail, int data, int pos):
- Purpose: Insert at a specific pos.
- How:
  1. Handle pos=1 (call insertAtHead).
  2. Else, traverse (temp) to node before pos.
  3. Insert: New node’s next to temp->next, temp->next to new node.
  4. Update tail if new node is last.
- Example: 10->20->40 + insertAtMiddle(..., 30, 3) → 10->20->30->40
deletePosition(Node* &head, int pos):
- Purpose: Delete node at specific pos.
- How:
  1. Handle pos=1 (update head, delete old head).
  2. Else, traverse (temp) to node before pos.
  3. Bypass target node (temp->next = target->next), delete target.
- Example: 10->20->30 + deletePosition(head, 2) → 10->30
deleteValue(Node* &head, int val):
- Purpose: Delete the first occurrence of val.
- How:
  1. Handle head->data == val (update head, delete old head).
  2. Else, use prev and temp to find val.
  3. Bypass temp (prev->next = temp->next), delete temp.
- Example: 10->20->30 + deleteValue(head, 20) → 10->30

4. `floydDetectLoop(Node* head)` Function (New!)

Purpose: Efficiently detect if a cycle (loop) is present in the linked list using Floyd’s Cycle-Finding Algorithm (also known as the Tortoise and Hare algorithm).
Concept: Uses two pointers, one moving slowly (1 step at a time) and one moving fast (2 steps at a time). If there’s a loop, the fast pointer will eventually catch up to the slow pointer. If no loop, the fast pointer will reach NULL.
How it works (Step-by-Step):
1. Empty List Check:
  - if(head == NULL): Returns false. An empty list cannot have a loop.
2. Initialize Pointers:
  - Node* slow = head;: Slow pointer starts at head.
  - Node* fast = head;: Fast pointer also starts at head.
3. Traverse and Check:
  - while(slow != NULL && fast != NULL): Loop as long as both pointers are valid.
  - fast = fast->next;: Fast pointer moves one step.
  - slow = slow->next;: Slow pointer moves one step.
  - if(fast != NULL): Check if fast is still valid before moving it a second time.
    - fast = fast->next;: Fast pointer moves a second step.
  - if(slow == fast): If the two pointers meet at any point, a loop is detected.
    - Return true (loop detected).
4. No Loop Confirmation:
  - If the loop finishes (meaning fast or slow became NULL), it indicates the fast pointer reached the end of the list without meeting the slow pointer.
  - Return false (no loop found).
Example:

Scenario 1: Non-Cyclic List head -> 1 -> 2 -> 3 -> 4 -> NULL

Iteration slow fast slow == fast?
Initial 1 1 true (initial)
1 2 3 false
2 3 NULL false
Loop Ends fast is NULL.
- Function returns false.
- Result: “Cycle is not present!”
Scenario 2: Cyclic List head -> 1 -> 2 -> 3 -> 4 -> 5 ^---------<--| (5 points back to 2)

Iteration slow fast slow == fast?
Initial 1 1 true (initial)
1 2 3 false
2 3 5 false
3 4 2 false
4 5 4 false
5 2 2 true
Loop Ends (Pointers met)
- Function returns true.
- Result: “Cycle is present!“

Iteration	`slow`	`fast`	`slow == fast`?
Initial	`1`	`1`	`true` (initial)
1	`2`	`3`	`false`
2	`3`	`NULL`	`false`
Loop Ends	`fast` is `NULL`.

Iteration	`slow`	`fast`	`slow == fast`?
Initial	`1`	`1`	`true` (initial)
1	`2`	`3`	`false`
2	`3`	`5`	`false`
3	`4`	`2`	`false`
4	`5`	`4`	`false`
5	`2`	`2`	`true`
Loop Ends	(Pointers met)

5. `main()` Function

Purpose: Test and demonstrate.
Flow:
1. Creates initial Node (head).
2. Populates list using insertAtTail.
3. Prints the original list.
4. (Optional: Uncomment tail->next = head->next->next->next; to create a cycle for testing).
5. Calls floydDetectLoop to check for a cycle.
6. Prints the result ("Cycle is present!" or "Cycle is not present!").

Flyod Cycle Detection

1. What is it?

2. Core Node Structure

3. Basic Operations (Quick Glance)

4. floydDetectLoop(Node* head) Function (New!)

5. main() Function

2. Core `Node` Structure

4. `floydDetectLoop(Node* head)` Function (New!)

5. `main()` Function