Detect Loop

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

// isCyclic: Detects if a cycle (loop) is present in the linked list
bool isCyclic(Node* head) {
    if(head == NULL) { // Empty list has no cycle
        return false;
    }

    map<Node*, bool> visited; // Map to store visited nodes (Node* -> bool)
    Node* temp = head;        // Start traversal from head

    // Traverse the list
    while(temp != NULL) {
        // If current node is already in 'visited' map and marked true, a cycle is found
        if(visited[temp] == true) {
            return true; // Cycle detected
        }

        visited[temp] = true; // Mark current node as visited
        temp = temp->next;    // Move to the next node
    }

    return false; // Reached end of list (temp is NULL), no cycle 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
    if(isCyclic(head)) {
        cout << "Cycle is present!" << endl;
    } else {
        cout << "Cycle is not present!" << endl;
    }

    return 0; // Indicate success
}

You are absolutely right! My apologies for the misunderstanding. It seems I misinterpreted “immersive” or thought it was a feature that made copying easier. I understand now you just want the raw Markdown text directly in the chat, without any special containers.

Here is the entire content of the quick revision notes, written directly as plain Markdown for easy copying:

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. `isCyclic(Node* head)` Function (New!)

Purpose: Detect if a cycle (loop) is present in the linked list.
Concept: If you traverse a list with a cycle, you will eventually revisit a node you’ve already seen. This function uses a hash map (std::map in C++) to keep track of visited nodes.
How it works (Step-by-Step):
1. Empty List Check:
  - if(head == NULL): Returns false. An empty list cannot have a cycle.
2. Initialize Visited Map:
  - map<Node*, bool> visited;: Creates a map where keys are Node* (node addresses) and values are bool (true if visited).
3. Initialize Traversal Pointer:
  - Node* temp = head;: Start temp at the head of the list.
4. Traverse and Check:
  - while(temp != NULL): Loop as long as temp hasn’t reached the end of the list.
  - Inside the loop:
    - if(visited[temp] == true): If the current node (temp) is already in the visited map and its value is true, it means we’ve encountered this node before.
      - Return true (cycle detected).
    - visited[temp] = true;: Mark the current node (temp) as visited in the map.
    - temp = temp->next;: Move temp to the next node.
5. No Cycle Confirmation:
  - If the loop finishes (temp becomes NULL), it means we traversed the entire list without revisiting any node.
  - Return false (no cycle found).
Example:

Scenario 1: Non-Cyclic List head -> 1 -> 2 -> 3 -> NULL
1. temp starts at 1.
2. temp moves: 1 → 2 → 3 → NULL.
3. When temp is NULL, loop ends. Returns false.
Scenario 2: Cyclic List head -> 1 -> 2 -> 3 -> 4 -> 5 ^---------<--| (5 points back to 2)
1. temp starts at 1.
2. temp moves: 1 → 2 → 3 → 4 → 5 → 2.
3. When temp is 2 again, visited[2] is true. Returns true.

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 isCyclic to check for a cycle.
6. Prints the result ("Cycle is present!" or "Cycle is not present!").

Detect Loop

1. What is it?

2. Core Node Structure

3. Basic Operations (Quick Glance)

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

5. main() Function

2. Core `Node` Structure

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

5. `main()` Function