Create a Circular Singly Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting nodes in a circular singly linked list?

Consider the following C code that creates a circular singly linked list by inserting nodes at the end. What will be the printed output?

DSA C

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void printList(Node* head) {
    if (head == NULL) return;
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    printList(head);
    return 0;
}

A 20 -> 30 -> 10 -> null

B 10 -> 20 -> 30 -> 10 -> null

C 10 -> 20 -> 30 -> null

D 10 -> 20 -> null

💡 Hint

Remember that in a circular singly linked list, the last node points back to the head, but printing stops when we reach the head again.

The printList function prints nodes starting from head and stops when it reaches head again. So it prints 10, 20, 30 and then stops, showing '10 -> 20 -> 30 -> null'.

🧠 Conceptual

intermediate

What is the key difference between a circular singly linked list and a normal singly linked list?

Choose the correct statement that best describes the difference between a circular singly linked list and a normal singly linked list.

A In a circular singly linked list, nodes have two pointers; in a normal singly linked list, nodes have one pointer.

B In a circular singly linked list, the last node points back to the head; in a normal singly linked list, the last node points to NULL.

C A circular singly linked list can only store integers; a normal singly linked list can store any data type.

D A circular singly linked list is always sorted; a normal singly linked list is not.

💡 Hint

Think about where the last node points in each list type.

The main difference is that in a circular singly linked list, the last node's next pointer points back to the head node, forming a circle. In a normal singly linked list, the last node points to NULL.

🔧 Debug

advanced

Why does this circular singly linked list insertion code cause an infinite loop?

Examine the code below. It tries to insert a node at the end of a circular singly linked list but causes an infinite loop. What is the bug?

DSA C

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void printList(Node* head) {
    if (head == NULL) return;
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 5);
    insertEnd(&head, 15);
    insertEnd(&head, 25);
    printList(head);
    return 0;
}

A The while loop condition should check for temp->next != *head instead of temp->next != NULL.

B The newNode->next should be set to NULL instead of *head.

C The createNode function does not allocate memory correctly.

D The printList function should use a while loop instead of do-while.

💡 Hint

In a circular list, the last node's next is not NULL.

The bug is in the while loop condition inside insertEnd. It checks for temp->next != NULL, but in a circular list, the last node points back to head, not NULL. So the loop never ends, causing an infinite loop.

❓ Predict Output

advanced

What is the output after deleting a node from a circular singly linked list?

Given the code below that deletes the node with value 20 from a circular singly linked list, what will be the printed output?

DSA C

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void deleteNode(Node** head, int key) {
    if (*head == NULL) return;
    Node *curr = *head, *prev = NULL;
    while (curr->data != key) {
        if (curr->next == *head) return; // key not found
        prev = curr;
        curr = curr->next;
    }
    if (curr == *head) {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        if (curr->next == *head) {
            free(curr);
            *head = NULL;
        } else {
            temp->next = curr->next;
            *head = curr->next;
            free(curr);
        }
    } else {
        prev->next = curr->next;
        free(curr);
    }
}

void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    deleteNode(&head, 20);
    printList(head);
    return 0;
}

A 10 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 20 -> 30 -> null

D List is empty

💡 Hint

After deleting 20, the list should contain the remaining nodes in order.

The node with data 20 is deleted. The list now contains 10 and 30 linked circularly. The printList prints '10 -> 30 -> null'.

🧠 Conceptual

expert

What is the time complexity of inserting a node at the end of a circular singly linked list without a tail pointer?

Consider a circular singly linked list with only a head pointer (no tail pointer). What is the time complexity of inserting a new node at the end of the list?

A O(log n), because the list is circular.

B O(1), because you can insert directly after the head.

C O(n^2), because each insertion requires traversing the entire list multiple times.

D O(n), because you must traverse the list to find the last node.

💡 Hint

Think about how to find the last node without a tail pointer.

Without a tail pointer, to insert at the end, you must traverse all nodes to find the last node, which takes O(n) time.

Practice

1. What is a key characteristic of a circular singly linked list compared to a regular singly linked list?

easy

A. The last node points back to the first node, forming a circle.

B. Each node has two pointers, one to the next and one to the previous node.

C. It uses an array internally to store nodes.

D. The list ends with a null pointer indicating the end.

Solution

1. Step 1: Understand the pointer structure in circular singly linked list

   In a circular singly linked list, the last node's next pointer points back to the first node, creating a loop.

2. Step 2: Compare with regular singly linked list

   Regular singly linked lists end with a null pointer, while circular ones loop back to the start.

3. Final Answer:

   The last node points back to the first node, forming a circle. -> Option A

4. Quick Check:

   Circular list last node points to head = C [OK]

Hint: Remember: circular means last node links back to first [OK]

Common Mistakes:

• Thinking circular list ends with null pointer
• Confusing circular singly linked list with doubly linked list
• Assuming nodes have two pointers in singly linked list

2. Which of the following is the correct way to initialize a circular singly linked list with one node in C?

easy

A. node->next = head->next;

B. node->next = NULL;

C. node->next = node;

D. node->next = 0;

Solution

1. Step 1: Understand initialization of single node circular list

   For a circular singly linked list with one node, the node's next pointer must point to itself to form a circle.

2. Step 2: Check each option

   node->next = node; sets node->next = node, correctly creating a self-loop. Others either set null or incorrect pointers.

3. Final Answer:

   node->next = node; -> Option C

4. Quick Check:

   Single node points to itself = A [OK]

Hint: Single node circular list points to itself [OK]

Common Mistakes:

• Setting next pointer to NULL instead of self
• Using uninitialized pointers
• Confusing NULL with 0 in pointer context

3. Consider the following C code snippet that creates a circular singly linked list with three nodes. What will be the output of the print loop?

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

int main() {
  Node n1 = {1, NULL};
  Node n2 = {2, NULL};
  Node n3 = {3, NULL};

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n1;  // circular link

  Node* temp = &n1;
  int count = 0;
  while (count < 5) {
    printf("%d ", temp->data);
    temp = temp->next;
    count++;
  }
  return 0;
}

medium

A. 1 2 3 3 3

B. 1 2 3 2 3

C. 1 2 3 1 1

D. 1 2 3 1 2

Solution

1. Step 1: Trace the linked list nodes and their next pointers

   n1 points to n2, n2 points to n3, n3 points back to n1, forming a circle: 1 -> 2 -> 3 -> 1 ...

2. Step 2: Follow the print loop for 5 iterations

   Print order: 1 (n1), 2 (n2), 3 (n3), 1 (n1 again), 2 (n2 again).

3. Final Answer:

   1 2 3 1 2 -> Option D

4. Quick Check:

   Loop prints nodes in circle: 1 2 3 1 2 [OK]

Hint: Follow next pointers in circle for given count [OK]

Common Mistakes:

• Stopping after 3 nodes instead of 5
• Not following circular link back to first node
• Confusing node data values

4. The following code attempts to create a circular singly linked list with two nodes. What is the error?

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

int main() {
  Node* n1 = malloc(sizeof(Node));
  Node* n2 = malloc(sizeof(Node));
  n1->data = 10;
  n2->data = 20;
  n1->next = n2;
  n2->next = NULL;  // mistake here
  return 0;
}

medium

A. Memory allocation is missing for nodes.

B. n2->next should point to n1 to make the list circular.

C. Data values are not initialized correctly.

D. n1->next should be NULL instead of n2.

Solution

1. Step 1: Identify the circular link requirement

   In a circular singly linked list, the last node's next pointer must point back to the first node.

2. Step 2: Check the code's next pointers

   n1->next points to n2, but n2->next is NULL, breaking the circle. It should point to n1.

3. Final Answer:

   n2->next should point to n1 to make the list circular. -> Option B

4. Quick Check:

   Last node next points to head = D [OK]

Hint: Last node's next must link to first node [OK]

Common Mistakes:

• Setting last node next to NULL instead of head
• Forgetting to allocate memory for nodes
• Mixing up which node points where

5. You want to insert a new node with data 5 at the end of an existing circular singly linked list. The list currently has nodes 1 -> 2 -> 3 -> (back to 1). Which steps correctly insert the new node to maintain the circular structure?

hard

A. Create new node; set new_node->next = head; find last node; set last_node->next = new_node;

B. Create new node; set new_node->next = NULL; find last node; set last_node->next = new_node;

C. Create new node; set new_node->next = last_node; set head = new_node;

D. Create new node; set new_node->next = head->next; set head->next = new_node;

Solution

1. Step 1: Create new node and link it to head

   The new node's next pointer must point to the head to keep the circle intact.

2. Step 2: Find the last node and update its next pointer

   Traverse the list to find the last node (which points to head), then set last_node->next to new_node.

3. Final Answer:

   Create new node; set new_node->next = head; find last node; set last_node->next = new_node; -> Option A

4. Quick Check:

   New node next = head, last node next = new node = A [OK]

Hint: New node next points to head; last node next points to new node [OK]

Common Mistakes:

• Setting new node next to NULL breaks circularity
• Not updating last node's next pointer
• Confusing head and last node pointers