Check Circular Linked List

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

// isCircular: Checks if the linked list is circular
bool isCircular(Node* head) {
    if(head == NULL) { // Empty list is considered circular (or trivial case)
        return true;
    }

    Node* temp = head->next; // Start from the second node

    // Traverse until temp hits head (circular) or NULL (not circular)
    while(temp != head) {
        if(temp == NULL) { // Reached end of list, not circular
            return false;
        }
        temp = temp->next; // Move to next node
    }

    return true; // Loop completed, temp is head, so it's circular
}

// 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 make it circular for testing:
    // tail->next = head; // Makes the list circular

    // Check if the list is circular
    if(isCircular(head)) {
        cout << "Circular List!" << endl;
    } else {
        cout << "Not a Circular List!" << endl;
    }

    return 0; // Indicate success
}

Understood! Here’s the complete revision guide in Markdown format, ready for you to copy and use.

---

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 what links everything together.

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. Advanced Operation: reverseInGroup(Node* head, int k)

• Purpose: Reverses the linked list in groups of k nodes.

• Approach: Recursive.

• How it works (Step-by-Step for each k-group):

  1. Reverse First K Nodes (Iterative):
     • Use prev, curr, next pointers.
     • Loop k times: next = curr->next; curr->next = prev; prev = curr; curr = next;
  2. Recursive Call:
     • If next (start of next group) is not NULL, link the original head (which is now the tail of the reversed group) to the result of reverseInGroup(next, k).
  3. Return New Head: Return prev (the new head of the current k-group).

• Example: Initial: 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3

  • Call 1 (reverseInGroup(1, 3)):
    • Reverses 1->2->3 into 3<-2<-1. prev is 3, curr is 4.
    • 1->next (original head) is set to reverseInGroup(4, 3).
  • Call 2 (reverseInGroup(4, 3)):
    • Reverses 4->5->6 into 6<-5<-4. prev is 6, curr is NULL.
    • Returns 6.
  • Back to Call 1: 1->next becomes 6.
  • Final Return: Call 1 returns 3.
  • Result: 3 -> 2 -> 1 -> 6 -> 5 -> 4

5. isCircular(Node* head) Function (New!)

• Purpose: Determine if a singly linked list forms a cycle.

• Concept: In a circular list, traversing from any node eventually returns to a previously visited node (specifically, head in this implementation’s logic). In a non-circular list, you reach NULL.

• How it works (Step-by-Step):

  1. Empty List Check:
     • if(head == NULL): Returns true (empty list can be considered trivially circular).
  2. Initialize Traversal Pointer:
     • Node* temp = head->next;
     • Start temp from the second node.
  3. Traverse and Check:
     • while(temp != head): Keep moving temp until it either hits head or NULL.
     • Inside Loop:
       • if(temp == NULL): If temp becomes NULL, we reached the end.
         • Return false (not circular).
       • temp = temp->next;: Move temp to the next node.
  4. Circular Confirmation:
     • If the loop finishes (temp == head), it means temp started at head->next and eventually came back to head.
     • Return true (it’s circular).

• Example:

  Scenario 1: Non-Circular List head -> 1 -> 2 -> 3 -> NULL

  1. temp starts at 2.
  2. temp moves: 2 → 3 → NULL.
  3. When temp is NULL, if(temp == NULL) is true. Returns false.

  Scenario 2: Circular List head -> 1 -> 2 -> 3 -> (points back to 1) (after tail->next = head; is uncommented)

  1. temp starts at 2.
  2. temp moves: 2 → 3 → 1.
  3. When temp is 1, while(temp != head) condition (1 != 1) becomes false, loop ends.
  4. Returns true.

6. 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; to make it circular).
  5. Calls isCircular to check its nature.
  6. Prints the result ("Circular List!" or "Not a Circular List!").

---