Detect if a Linked List is Circular in DSA C

Mental Model

We want to check if the list loops back to an earlier node instead of ending.

Analogy: Imagine walking down a path and checking if you ever step on the same stone twice, meaning the path loops.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 2 (circular back to node with value 2)

Goal: Detect if the list has a loop by finding if any node repeats in the path

Step 1: slow pointer moves to node 2, fast pointer moves to node 3

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 2 (loop)

Why: Start moving pointers at different speeds to detect cycle

Step 2: slow pointer moves to node 3, fast pointer moves to node 2 (loop)

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->2] (loop)

Why: Fast pointer moves twice as fast, may catch slow pointer if cycle exists

Step 3: slow pointer moves to node 4, fast pointer moves to node 4

head -> 1 -> 2 -> 3 -> [slow->4] -> [fast->4] (loop)

Why: Pointers meet at same node, confirming cycle

Result:

head -> 1 -> 2 -> 3 -> 4 -> 2 (loop detected) -> true

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

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

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect if linked list is circular
int isCircular(Node* head) {
    if (head == NULL) return 0; // empty list is not circular

    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // move slow by 1
        fast = fast->next->next; // move fast by 2

        if (slow == fast) {
            return 1; // cycle detected
        }
    }
    return 0; // no cycle
}

// Driver code
int main() {
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    // Creating a cycle: last node points back to node with value 2
    head->next->next->next->next = head->next;

    if (isCircular(head)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

if (head == NULL) return 0; // empty list is not circular

handle empty list edge case

slow = slow->next; // move slow by 1

advance slow pointer by one node

fast = fast->next->next; // move fast by 2

advance fast pointer by two nodes

if (slow == fast) { return 1; }

if pointers meet, cycle detected

Output

true

Complexity Analysis

Time: O(n) because we traverse nodes with two pointers at different speeds, meeting quickly if cycle exists

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Naive approach uses extra memory to store visited nodes (O(n) space), this uses constant space and is faster

Edge Cases

empty list

returns false because no nodes exist

DSA C

if (head == NULL) return 0; // empty list is not circular

single node pointing to itself

detects cycle because slow and fast meet immediately

DSA C

if (slow == fast) { return 1; }

list with no cycle

returns false after fast pointer reaches null

DSA C

while (fast != NULL && fast->next != NULL)

When to Use This Pattern

When you need to check if a linked list loops back on itself, use two pointers moving at different speeds to detect cycles efficiently.

Common Mistakes

Mistake: Not checking if fast or fast->next is NULL before moving fast pointer
Fix: Add condition while (fast != NULL && fast->next != NULL) to avoid null pointer errors

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to know if a linked list loops back to an earlier node.

If two pointers moving at different speeds meet, the list is circular.

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