Detect if a Linked List is Circular in DSA C++ - Deep Dive

Overview - Detect if a Linked List is Circular

What is it?

A linked list is a chain of nodes where each node points to the next one. Sometimes, the last node points back to an earlier node, forming a loop or circle. Detecting if a linked list is circular means checking if such a loop exists. This helps avoid infinite loops when processing the list.

Why it matters

Without detecting circular linked lists, programs can get stuck forever following the loop, causing crashes or freezes. This problem appears in many real systems like network routing or memory management. Detecting circularity helps keep programs safe and efficient.

Where it fits

Before this, you should understand what a linked list is and how nodes connect. After this, you can learn about removing loops, finding loop start points, or advanced linked list operations.

Mental Model

Core Idea

If you follow the next links in a linked list forever and come back to a node you already saw, the list is circular.

Think of it like...

Imagine walking down a path where each signpost points to the next one. If you ever reach a signpost you've seen before, you are walking in a circle.

Start -> Node1 -> Node2 -> Node3 -> Node4
                      ↑                      ↓
                      ←←←←←←←←←←←←←←←←←←

Build-Up - 6 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect using pointers.

A linked list is made of nodes. Each node has data and a pointer to the next node. The last node points to null if the list ends normally.

Result

You can represent a sequence of items connected by pointers ending with null.

Knowing the basic structure is essential before checking if the list loops back on itself.

2

Foundation

What Makes a Linked List Circular

Concept: Understand how a loop forms when a node points back to an earlier node instead of null.

If any node's next pointer points to a previous node in the list, the list forms a circle. This means no node points to null, and traversal can go on forever.

Result

A circular linked list has no end and cycles through nodes repeatedly.

Recognizing the difference between normal and circular lists helps identify the problem to solve.

3

Intermediate

Naive Loop Detection by Visited Nodes

🤔Before reading on: Do you think storing all visited nodes is efficient for detecting loops? Commit to yes or no.

Concept: Use extra memory to remember nodes visited and check if a node repeats.

Traverse the list, storing each node's address in a set. If you reach a node already in the set, a loop exists. If you reach null, no loop.

Result

Detects loops correctly but uses extra memory proportional to list size.

This method works but is not memory efficient, motivating better approaches.

4

Intermediate

Floyd's Cycle Detection Algorithm

🤔Before reading on: Will two pointers moving at different speeds always meet if a loop exists? Commit to yes or no.

Concept: Use two pointers moving at different speeds to detect a loop without extra memory.

Use a slow pointer moving one step and a fast pointer moving two steps each time. If they meet, a loop exists. If fast reaches null, no loop.

Result

Detects loops in O(n) time and O(1) space efficiently.

Using two pointers cleverly avoids extra memory and speeds up detection.

5

Advanced

Implementing Floyd's Algorithm in C++

🤔Before reading on: Do you think the fast pointer can skip over the slow pointer without meeting? Commit to yes or no.

Concept: Write code to detect circular linked list using two pointers in C++.

#include struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; bool isCircular(Node* head) { if (!head) return false; Node* slow = head; Node* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); // Creating a loop for testing head->next->next->next->next = head->next; std::cout << (isCircular(head) ? "List is circular" : "List is not circular") << std::endl; return 0; }

Result

Output: List is circular

Seeing the code in action confirms the two-pointer method's correctness and efficiency.

6

Expert

Why Two Pointers Always Meet in a Loop

🤔Before reading on: Do you think the fast pointer can avoid the slow pointer indefinitely in a loop? Commit to yes or no.

Concept: Understand the mathematical reasoning why two pointers moving at different speeds must meet inside a loop.

Inside a loop, the fast pointer moves two steps while the slow moves one. The distance between them decreases by one each step modulo loop length. Eventually, they meet because the gap closes.

Result

Guarantees detection of loops without extra memory or infinite waiting.

Knowing the proof builds confidence in the algorithm's reliability and helps debug tricky cases.

Under the Hood

The two-pointer method works because the fast pointer laps the slow pointer inside the loop. The slow pointer moves step-by-step, while the fast pointer moves twice as fast. If a loop exists, the fast pointer will eventually catch up to the slow pointer inside the cycle. If no loop exists, the fast pointer reaches the end (null) first.

Why designed this way?

This approach was designed to detect loops efficiently without extra memory. Earlier methods used extra space to track visited nodes, which is costly. Floyd's algorithm cleverly uses pointer speeds to detect cycles in linear time and constant space, making it practical for large lists.

Head
  ↓
+------+     +------+     +------+     +------+
| Node | --> | Node | --> | Node | --> | Node | --+
+------+     +------+     +------+     +------+   |
                                                  |
                                                  +-- back to second Node (loop)

Myth Busters - 3 Common Misconceptions

Quick: Does a linked list with a loop always have all nodes connected in the loop? Commit yes or no.

Common Belief: If a linked list is circular, all nodes form the loop.

Reality: Only some nodes form the loop; nodes before the loop start are outside the cycle.

Why it matters: Misunderstanding this can cause errors when trying to remove loops or count nodes.

Quick: Can the fast pointer skip over the slow pointer without meeting in Floyd's algorithm? Commit yes or no.

Common Belief: The fast pointer might skip the slow pointer and never meet.

Reality: They must meet eventually inside the loop due to their relative speeds.

Why it matters: Believing otherwise may lead to incorrect code or infinite loops.

Quick: Is extra memory always needed to detect loops in linked lists? Commit yes or no.

Common Belief: You must store visited nodes to detect loops.

Reality: Floyd's algorithm detects loops without extra memory.

Why it matters: Using extra memory unnecessarily wastes resources and reduces performance.

Expert Zone

1

The meeting point of slow and fast pointers is not necessarily the loop start; additional steps are needed to find the exact loop entry.

2

If the list is very large, the fast pointer may reach null quickly, so always check for null before moving pointers to avoid crashes.

3

Modifying the list during detection (like changing pointers) can break the algorithm; detection should be read-only.

When NOT to use

Avoid Floyd's algorithm if you need to find the exact start of the loop immediately; use extended algorithms like Floyd's with loop start detection or hashing methods. Also, if the list nodes cannot be compared by pointer equality (e.g., in some managed languages), alternative methods may be needed.

Production Patterns

In real systems, loop detection is used in garbage collectors to detect cyclic references, in network routing to detect loops, and in debugging tools to find infinite loops in data structures. Often combined with loop removal or safe traversal methods.

Connections

Cycle Detection in Graphs

Builds-on the idea of detecting cycles but in more complex structures with multiple paths.

Understanding linked list cycle detection helps grasp graph cycle detection algorithms like DFS and Union-Find.

Memory Leak Detection

Uses similar cycle detection to find unreachable but cyclically referenced objects in memory.

Knowing linked list loops aids understanding how garbage collectors detect and clean cyclic memory leaks.

Race Conditions in Concurrent Systems

Both involve detecting repeating states or conditions that cause infinite loops or deadlocks.

Recognizing cycles in data structures parallels detecting repeated states in concurrent processes, improving debugging skills.

Common Pitfalls

#1 Not checking if fast or fast->next is null before moving pointers.

Wrong approach:

while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}

Correct approach:

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}

Root cause:

Assuming fast->next is always valid leads to null pointer dereference and crashes.

#2 Using equality of node data instead of node pointers to detect loops.

Wrong approach:

if (slow->data == fast->data) return true;

Correct approach:

if (slow == fast) return true;

Root cause:

Data can repeat in different nodes; only pointer equality confirms the same node.

#3 Modifying the list during detection, like changing next pointers.

Wrong approach:

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
slow->next = nullptr; // wrong modification
if (slow == fast) return true;
}

Correct approach:

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}

Root cause:

Changing pointers breaks the list structure and invalidates detection logic.

Key Takeaways

A circular linked list has a loop where nodes point back to earlier nodes, causing infinite traversal.

Floyd's Cycle Detection Algorithm uses two pointers moving at different speeds to detect loops efficiently without extra memory.

The fast pointer will always meet the slow pointer inside a loop, guaranteeing detection.

Checking pointer equality, not data equality, is essential to correctly detect loops.

Proper null checks prevent crashes during traversal and detection.

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