Detect if a Linked List is Circular in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Circular Linked List Detection Function

What is the output of the following C++ code that checks if a linked list is circular?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool isCircular(Node* head) {
    if (!head) return false;
    Node* temp = head->next;
    while (temp != nullptr && temp != head) {
        temp = temp->next;
    }
    return (temp == head);
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = head; // Making list circular
    bool result = isCircular(head);
    if (result) {
        printf("Circular\n");
    } else {
        printf("Not Circular\n");
    }
    return 0;
}

A Compilation Error

B Not Circular

C Runtime Error

D Circular

💡 Hint

Think about how the function moves through the list and what condition it checks to decide circularity.

The function starts from the node after head and moves forward. If it reaches back to head, the list is circular. Since the last node points back to head, the function returns true and prints 'Circular'.

🧠 Conceptual

intermediate

Understanding Circular Linked List Detection Logic

Which statement best describes how the function detects if a linked list is circular?

A It traverses nodes until it finds a node pointing back to the head or reaches null.

B It uses two pointers moving at different speeds to detect a loop.

C It counts nodes and compares with a fixed number to decide circularity.

D It checks if any node's next pointer is null to confirm circularity.

💡 Hint

Focus on the stopping conditions of the traversal in the function.

The function moves through the list starting from the second node. It stops if it reaches null (not circular) or if it reaches the head again (circular).

🔧 Debug

advanced

Identify the Error in Circular Linked List Detection Code

What error will occur when running this code snippet to detect circular linked list?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool isCircular(Node* head) {
    if (!head) return false;
    Node* temp = head->next;
    while (temp != nullptr && temp != head) {
        temp = temp->next;
    }
    return (temp == head);
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = head->next; // Cycle created: 3 -> 2 (not back to head)
    bool result = isCircular(head);
    if (result) {
        printf("Circular\n");
    } else {
        printf("Not Circular\n");
    }
    return 0;
}

A Compilation error due to missing semicolon

B Infinite loop

C Correctly prints 'Not Circular'

D Runtime segmentation fault

💡 Hint

Check the initial value of temp and the loop condition carefully.

temp starts at head->next (node 2). The traversal enters the cycle 2 -> 3 -> 2, never reaching nullptr or head, causing an infinite loop.

❓ Predict Output

advanced

Output of Circular Linked List Detection with Single Node

What is the output of this code that checks if a single-node linked list is circular?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool isCircular(Node* head) {
    if (!head) return false;
    Node* temp = head->next;
    while (temp != nullptr && temp != head) {
        temp = temp->next;
    }
    return (temp == head);
}

int main() {
    Node* head = new Node(10);
    head->next = head; // Single node pointing to itself
    bool result = isCircular(head);
    if (result) {
        printf("Circular\n");
    } else {
        printf("Not Circular\n");
    }
    return 0;
}

A Circular

B Not Circular

C Runtime Error

D Compilation Error

💡 Hint

Consider what happens when the single node points to itself.

Since the single node points to itself, the traversal reaches back to head immediately, so the function returns true and prints 'Circular'.

🧠 Conceptual

expert

Why is Floyd’s Cycle Detection Algorithm Preferred Over Simple Traversal?

Why is Floyd’s Cycle Detection (tortoise and hare) algorithm preferred for detecting circular linked lists instead of simple traversal checking if next is head?

A Because it only works for singly linked lists with a head pointer.

B Because it requires less memory by storing visited nodes in a hash set.

C Because it uses two pointers moving at different speeds to detect cycles anywhere, not just if the list loops back to head.

D Because it modifies the linked list structure to mark visited nodes.

💡 Hint

Think about detecting cycles that do not necessarily loop back to the head node.

Floyd’s algorithm detects any cycle in the list by using two pointers moving at different speeds. It can detect loops anywhere, not just those that point back to the head.

Practice

1. What does it mean if a linked list is circular?

easy

A. The linked list nodes are sorted in ascending order

B. The linked list has no nodes

C. The last node points back to one of the previous nodes, forming a loop

D. The linked list has only one node

Solution

1. Step 1: Understand linked list structure

   A linked list is a chain of nodes where each node points to the next node.

2. Step 2: Define circular linked list

   If the last node points back to any previous node, it creates a loop, making the list circular.

3. Final Answer:

   The last node points back to one of the previous nodes, forming a loop -> Option C

4. Quick Check:

   Circular linked list = last node points back [OK]

Hint: Circular means last node links back to earlier node [OK]

Common Mistakes:

• Thinking circular means sorted list
• Confusing empty list with circular list
• Assuming single node list is always circular

2. Which of the following C++ code snippets correctly checks if a linked list is circular using a slow and fast pointer approach?

easy

A. while(slow != nullptr) { slow = slow->next; if(slow == fast) return true; } return false;

B. while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false;

C. for(int i=0; i<10; i++) { if(slow == fast) return true; slow = slow->next; fast = fast->next; } return false;

D. if(head == nullptr) return true; else return false;

Solution

1. Step 1: Understand slow and fast pointer method

   Two pointers move at different speeds; if they meet, a loop exists.

2. Step 2: Analyze code correctness

   while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; correctly moves slow by one and fast by two nodes, checking for equality inside the loop.

3. Final Answer:

   while(fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; -> Option B

4. Quick Check:

   Slow-fast pointer meeting means circular [OK]

Hint: Fast pointer moves twice as fast; meeting means loop [OK]

Common Mistakes:

• Not checking fast and fast->next for nullptr
• Moving pointers at same speed
• Returning true without pointer meeting

3. What will be the output of the following C++ code snippet?

struct Node {
  int data;
  Node* next;
};

Node* head = new Node{1, nullptr};
Node* second = new Node{2, nullptr};
Node* third = new Node{3, nullptr};
head->next = second;
second->next = third;
third->next = second; // creates a loop

bool isCircular(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while(fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast) return true;
  }
  return false;
}

std::cout << (isCircular(head) ? "Circular" : "Not Circular") << std::endl;

medium

A. Circular

B. Not Circular

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Analyze linked list structure

   third->next points to second, creating a loop between second and third nodes.

2. Step 2: Trace slow and fast pointers

   Slow moves one step, fast moves two steps; they will meet inside the loop, returning true.

3. Final Answer:

   Circular -> Option A

4. Quick Check:

   Loop detected by slow-fast pointers = Circular [OK]

Hint: Loop causes slow and fast pointers to meet [OK]

Common Mistakes:

• Ignoring the loop created by third->next
• Assuming no loop means Not Circular
• Confusing pointer assignments

4. Identify the error in the following code that attempts to detect if a linked list is circular:

bool isCircular(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while(fast != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast) return true;
  }
  return false;
}

medium

A. The loop condition should check fast->next != nullptr to avoid null pointer dereference

B. The slow pointer should move two steps instead of one

C. The function should return false inside the loop

D. The function should initialize slow and fast to nullptr

Solution

1. Step 1: Check loop condition safety

   fast->next->next is accessed, so fast->next must not be nullptr to avoid crash.

2. Step 2: Correct loop condition

   Change while(fast != nullptr) to while(fast != nullptr && fast->next != nullptr) to prevent null pointer dereference.

3. Final Answer:

   The loop condition should check fast->next != nullptr to avoid null pointer dereference -> Option A

4. Quick Check:

   Check fast and fast->next to avoid crash [OK]

Hint: Always check fast->next before fast->next->next [OK]

Common Mistakes:

• Not checking fast->next leads to runtime error
• Moving slow pointer incorrectly
• Returning false too early

5. You have a singly linked list where the last node might point back to any node, making it circular. How would you modify the list to remove the circular link and make it linear again?

hard

A. Set head to nullptr to clear the list

B. Delete all nodes after the head node

C. Reverse the linked list to break the loop

D. Detect the loop using slow and fast pointers, then find the node before the loop start and set its next to nullptr

Solution

1. Step 1: Detect loop using slow and fast pointers

   Use two pointers moving at different speeds; if they meet, a loop exists.

2. Step 2: Find the node before loop start and break the loop

   Reset one pointer to head, move both one step until they meet; the node before meeting point is loop end. Set its next to nullptr.

3. Final Answer:

   Detect the loop using slow and fast pointers, then find the node before the loop start and set its next to nullptr -> Option D

4. Quick Check:

   Find loop start, break link to remove circular [OK]

Hint: Find loop start, set previous node's next to nullptr [OK]

Common Mistakes:

• Deleting nodes unnecessarily
• Reversing list does not remove loop
• Setting head to nullptr loses entire list