Detect if a Linked List is Circular in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a linked list to be circular?

A linked list is circular if its last node points back to any previous node in the list, creating a loop instead of ending with a null pointer.

intermediate

Which pointer technique is commonly used to detect a cycle in a linked list?

The Floyd’s Cycle-Finding Algorithm uses two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. If they meet, the list is circular.

intermediate

What is the time complexity of detecting a circular linked list using Floyd’s Cycle-Finding Algorithm?

The time complexity is O(n), where n is the number of nodes in the linked list, because each pointer traverses the list at most once.

beginner

Why can’t we just check if the last node’s next pointer is NULL to detect circularity?

Because in a circular linked list, the last node’s next pointer points to a previous node, not NULL. But if the list is very large or has no explicit end, we need a method to detect loops without traversing infinitely.

beginner

What happens if the fast pointer reaches NULL in Floyd’s Cycle-Finding Algorithm?

If the fast pointer reaches NULL, it means the linked list has an end and is not circular.

What does the slow pointer do in Floyd’s Cycle-Finding Algorithm?

A Moves two nodes at a time

B Jumps to the end of the list

C Moves one node at a time

D Stays at the head node

The slow pointer moves one node at a time to help detect cycles by eventually meeting the fast pointer if a loop exists.

If a linked list is not circular, what will happen to the fast pointer?

A It will eventually point to NULL

B It will meet the slow pointer

C It will loop infinitely

D It will point to the head node

In a non-circular linked list, the fast pointer will reach the end and point to NULL.

Which of these is a sign that a linked list is circular?

A Last node’s next pointer is NULL

B Slow and fast pointers meet at some node

C List length is zero

D Head node is NULL

If slow and fast pointers meet, it means the list has a cycle and is circular.

What is the main advantage of Floyd’s Cycle-Finding Algorithm?

A Uses extra memory to store visited nodes

B Sorts the linked list

C Deletes circular nodes

D Detects cycle without extra memory

Floyd’s algorithm detects cycles using two pointers without extra memory.

What is the first step in detecting if a linked list is circular?

A Initialize slow and fast pointers at head

B Check if head is NULL

C Count the number of nodes

D Reverse the linked list

The algorithm starts by setting both slow and fast pointers at the head node.

Explain how Floyd’s Cycle-Finding Algorithm detects a circular linked list.

Think about how two runners on a track can meet if the track loops.

Describe why detecting a circular linked list is important before traversing it.

Imagine walking in circles without knowing it.

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