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.