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

Concept Flow - Detect if a Linked List is Circular

Start at head

↓

Check if current is NULL?

Yes→No cycle, end

No↓

Move to current.next

↓

Check if current == head?

Yes→Cycle detected, end

↩Back to Check if current is NULL?

Start from the head node and move through each node. If you reach NULL, no cycle exists. If you return to the head, a cycle is detected.

Execution Sample

DSA C

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

bool isCircular(struct Node* head) {
  struct Node* current = head;
  if (head == NULL) return false;
  while (current != NULL) {
    current = current->next;
    if (current == head) return true;
  }
  return false;
}

This code checks if a linked list loops back to the head, indicating a circular list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1->2->3->NULL	current = head (1)	1 -> 2 -> 3 -> NULL
2	Check current != NULL	1->2->3->NULL	current = 1 (not NULL)	1 -> 2 -> 3 -> NULL
3	Move current to current.next	1->2->3->NULL	current = 2	1 -> 2 -> 3 -> NULL
4	Check current == head?	1->2->3->NULL	current = 2 (not head)	1 -> 2 -> 3 -> NULL
5	Check current != NULL	1->2->3->NULL	current = 2 (not NULL)	1 -> 2 -> 3 -> NULL
6	Move current to current.next	1->2->3->NULL	current = 3	1 -> 2 -> 3 -> NULL
7	Check current == head?	1->2->3->NULL	current = 3 (not head)	1 -> 2 -> 3 -> NULL
8	Check current != NULL	1->2->3->NULL	current = 3 (not NULL)	1 -> 2 -> 3 -> NULL
9	Move current to current.next	1->2->3->NULL	current = NULL	1 -> 2 -> 3 -> NULL
10	Check current == head?	1->2->3->NULL	current = NULL (not head)	1 -> 2 -> 3 -> NULL
11	Check current != NULL	1->2->3->NULL	current = NULL (is NULL)	1 -> 2 -> 3 -> NULL
12	No cycle found, return false	1->2->3->NULL	current = NULL	1 -> 2 -> 3 -> NULL

💡 current reached NULL, so the list is not circular

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
current	head (1)	2	3	NULL	NULL	NULL	NULL

Key Moments - 3 Insights

Why do we check if current == head inside the loop?

Because if current points back to head, it means the list loops and is circular. This is shown in execution_table rows 4, 7, and 10 where the check happens.

Why do we stop when current becomes NULL?

If current is NULL, it means we reached the end of the list without looping back, so no cycle exists. This is shown in execution_table row 11.

What if the list is empty (head is NULL)?

The loop never runs because current starts as NULL, so the function returns false immediately, meaning no cycle.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current at Step 6?

A 2

B 3

C NULL

D head (1)

💡 Hint

Check the 'Pointer Changes' column at Step 6 in execution_table.

At which step does the condition current != NULL become false?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns where current becomes NULL.

If the list was circular, at which step would the function return true?

A When current equals head again

B At the start before the loop

C When current becomes NULL

D When current is the last node

💡 Hint

Refer to the 'Operation' column checking if current == head inside the loop.

Concept Snapshot

Detect if a Linked List is Circular:
- Start from head node
- Move current pointer through next nodes
- If current becomes NULL, list is not circular
- If current points back to head, list is circular
- Return true if cycle found, else false

Full Transcript

To detect if a linked list is circular, start at the head node and move through each node using a pointer called current. At each step, check if current is NULL. If yes, the list ends and is not circular. If current points back to the head node, a cycle exists and the list is circular. The code moves current to current.next repeatedly until one of these conditions is met. This method ensures we detect loops by seeing if we return to the start node.

Practice

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

easy

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

B. The linked list has no nodes

C. The linked list nodes are sorted in ascending order

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: Identify circular linked list property

   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 A

4. Quick Check:

   Circular linked list = last node points back [OK]

Hint: Circular means last node links back inside list [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly checks if a linked list is circular?

easy

A. for (int i = 0; i < 10; i++) { head = head->next; } return 0;

B. if (head == NULL) return 1; else return 0;

C. while (head->next != NULL) { head = head->next; } return 1;

D. while (head != NULL) { head = head->next; if (head == start) return 1; } return 0;

Solution

1. Step 1: Analyze code logic for circular detection

   The code moves through nodes until it finds the start node again, indicating a loop.

2. Step 2: Check other options for correctness

   if (head == NULL) return 1; else return 0; only checks if list is empty, not circular. while (head->next != NULL) { head = head->next; } return 1; stops at NULL, no loop check. for (int i = 0; i < 10; i++) { head = head->next; } return 0; blindly moves 10 steps without loop check.

3. Final Answer:

   while (head != NULL) { head = head->next; if (head == start) return 1; } return 0; -> Option D

4. Quick Check:

   Loop check by revisiting start node = while (head != NULL) { head = head->next; if (head == start) return 1; } return 0; [OK]

Hint: Check if traversal returns to start node [OK]

Common Mistakes:

• Only checking for NULL without loop detection
• Using fixed iteration count instead of loop condition
• Returning true for empty list

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

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

int isCircular(Node* head) {
  if (head == NULL) return 0;
  Node* temp = head->next;
  while (temp != NULL && temp != head) {
    temp = temp->next;
  }
  return (temp == head);
}

int main() {
  Node a, b, c;
  a.data = 1; b.data = 2; c.data = 3;
  a.next = &b; b.next = &c; c.next = &a;
  printf("%d", isCircular(&a));
  return 0;
}

medium

A. Runtime error

B. 0

C. 1

D. Compilation error

Solution

1. Step 1: Understand linked list setup

   Nodes a, b, c are linked in a circle: a->b->c->a.

2. Step 2: Trace isCircular function

   Function moves temp pointer until it finds head again or NULL. Here, temp will reach head again, so returns 1.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   Loop detected, returns 1 [OK]

Hint: Returns 1 if traversal loops back to head [OK]

Common Mistakes:

• Assuming NULL termination means circular
• Confusing return values 0 and 1
• Not initializing temp correctly

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

int isCircular(Node* head) {
  Node* slow = head;
  Node* fast = head->next;
  while (fast != NULL && fast->next != NULL) {
    if (slow == fast) return 1;
    slow = slow->next;
    fast = fast->next->next;
  }
  return 0;
}

medium

A. slow pointer should move two steps, fast one step

B. fast pointer initialization should be head, not head->next

C. The loop condition should check only fast != NULL

D. Return values are reversed

Solution

1. Step 1: Understand Floyd's cycle detection setup

   Both slow and fast pointers should start at head to detect cycle properly.

2. Step 2: Identify initialization error

   fast is initialized to head->next, which can miss cycle detection if list has only one node or cycle starts at head.

3. Final Answer:

   fast pointer initialization should be head, not head->next -> Option B

4. Quick Check:

   Initialize fast = head for correct cycle detection [OK]

Hint: Start both pointers at head for Floyd's cycle detection [OK]

Common Mistakes:

• Starting fast pointer one step ahead
• Swapping slow and fast pointer steps
• Ignoring null checks in loop condition

5. You have a singly linked list where the last node's next pointer is unknown. How would you modify the list to make it circular and then detect the cycle using Floyd's algorithm? Choose the correct sequence of steps.

hard

A. 1. Traverse to last node
2. Set last node's next to head
3. Use Floyd's algorithm to detect cycle

B. 1. Set head's next to NULL
2. Use Floyd's algorithm
3. Traverse list

C. 1. Reverse the list
2. Set last node's next to NULL
3. Use Floyd's algorithm

D. 1. Traverse to middle node
2. Set middle node's next to head
3. Use Floyd's algorithm

Solution

1. Step 1: Make the list circular by linking last node to head

   Traverse the list to find the last node, then set its next pointer to head to form a loop.

2. Step 2: Apply Floyd's cycle detection algorithm

   Use slow and fast pointers starting at head to detect the cycle created.

3. Final Answer:

   1. Traverse to last node 2. Set last node's next to head 3. Use Floyd's algorithm to detect cycle -> Option A

4. Quick Check:

   Make circular then detect cycle with Floyd's algorithm [OK]

Hint: Link last node to head before running cycle detection [OK]

Common Mistakes:

• Setting wrong node's next pointer
• Not traversing to last node correctly
• Using Floyd's algorithm before making list circular