Detect if a Linked List is Circular in DSA C++ - Execution Trace

Concept Flow - Detect if a Linked List is Circular

Start at head

↓

Initialize slow and fast pointers

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

Yes→List is Circular

No↓

Check if fast or fast->next is NULL?

Yes→List is NOT Circular

↩Back to Move slow by 1 step

Start with two pointers moving at different speeds; if they meet, the list is circular; if fast pointer reaches end, it's not.

Execution Sample

DSA C++

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

This code uses two pointers moving at different speeds to detect if the linked list loops back on itself.

Execution Table

Step	Operation	slow Pointer	fast Pointer	Check slow == fast	List State	Visual State
1	Initialize pointers	Node1	Node1	No	Unknown	Node1 -> Node2 -> Node3 -> Node2 (loop)
2	Move slow by 1	Node2	Node1	No	Unknown	Node1 -> Node2 -> Node3 -> Node2 (loop)
3	Move fast by 2	Node2	Node3	No	Unknown	Node1 -> Node2 -> Node3 -> Node2 (loop)
4	Move slow by 1	Node3	Node3	Yes	Circular detected	Node1 -> Node2 -> Node3 -> Node2 (loop)
5	Return true	-	-	-	Circular detected	Node1 -> Node2 -> Node3 -> Node2 (loop)

💡 slow and fast pointers met at Node3, confirming the list is circular

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
slow	Node1	Node2	Node2	Node3	Node3
fast	Node1	Node1	Node3	Node3	Node3

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one?

Moving fast pointer twice as fast ensures that if there is a loop, fast will eventually catch slow inside the loop, as shown in execution_table rows 3 and 4.

What happens if the list is not circular?

If the list is not circular, fast or fast->next will become NULL, causing the loop to stop and return false. This is not shown here but would be the exit condition.

Why do we check slow == fast after moving pointers?

Checking slow == fast after moving pointers detects if both pointers meet inside the loop, confirming circularity, as seen in step 4 of execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what node is the slow pointer at after step 3?

A Node3

B Node2

C Node1

D Node4

💡 Hint

Check the 'slow Pointer' column in execution_table row for step 3.

At which step do slow and fast pointers meet?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Check slow == fast' column in execution_table to find when it becomes 'Yes'.

If the list was not circular, what would happen to the fast pointer?

A It would eventually become NULL

B It would meet slow pointer

C It would stay at head

D It would move only one step

💡 Hint

Refer to the concept_flow where fast or fast->next being NULL stops the loop.

Concept Snapshot

Detect Circular Linked List:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until fast or fast->next is NULL (not circular)
- If slow == fast at any point, list is circular
- Return true if circular, else false
- Efficient: O(n) time, O(1) space

Full Transcript

To detect if a linked list is circular, we use two pointers starting at the head. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If the list has a loop, the fast pointer will eventually catch up to the slow pointer inside the loop. If the fast pointer reaches the end (NULL), the list is not circular. This method efficiently detects loops without extra memory. The code initializes both pointers at the head, then moves them step by step, checking if they meet. If they meet, the function returns true, indicating a circular list. Otherwise, it returns false when the fast pointer reaches the end.

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