.png)
Singly to Circular Linked List Conversion
Problem Statement
Given a singly linked list, convert it into a circular linked list by modifying the next pointer of the last node so that it points to the head node.
In a singly linked list, the last node points to NULL. After conversion, the last node should point back to the first node, forming a circular structure.
Example
Input
Singly Linked List:
10 → 20 → 30 → 40 → NULL
Output
Circular Linked List:
10 → 20 → 30 → 40 → back to 10
Approach: Traverse to Last Node and Link to Head
Approach Explanation
To convert a singly linked list into a circular linked list:
- Traverse the list to find the last node
- Update the next pointer of the last node to point to the head
- This maintains all existing nodes and simply modifies one pointer
This approach is simple, efficient, and does not require extra memory.
Algorithm
- If head == NULL, return (empty list cannot be converted).
- Initialize a pointer current = head.
- Traverse the list until current->next == NULL.
- Set current->next = head.
- The singly linked list is now converted into a circular linked list.
Time Complexity
- Best Case: O(1) (single node list)
- Worst Case: O(n)
- Average Case: O(n)
Space Complexity
- O(1)
No additional memory is used.
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
// Function to convert singly linked list to circular
void convertToCircular(struct Node* head) {
if (head == NULL)
return;
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = head;
}
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to print circular linked list
void printCircular(struct Node* head) {
if (head == NULL)
return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to head)\n");
}
int main() {
// Creating linked list: 1 -> 2 -> 3 -> 4
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
// Convert to circular
convertToCircular(head);
// Print circular list
printCircular(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* next;
};
// Convert singly linked list to circular
void convertToCircular(Node* head) {
if (head == NULL)
return;
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = head;
}
// Create new node
Node* createNode(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Print circular linked list
void printCircular(Node* head) {
if (head == NULL)
return;
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(back to head)" << endl;
}
int main() {
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
head->next->next->next->next = createNode(5);
convertToCircular(head);
printCircular(head);
return 0;
}Java Implementation
static void convertToCircular(Node head) {
if (head == null)
return;
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = head;
}
Python Implementation
def convert_to_circular(head):
if head is None:
return
current = head
while current.next is not None:
current = current.next
current.next = head
JavaScript Implementation
function convertToCircular(head) {
if (head === null)
return;
let current = head;
while (current.next !== null) {
current = current.next;
}
current.next = head;
}
Output-
1 -> 2 -> 3 -> 4 -> (back to head)Edge Cases to Consider
- Empty linked list
- Single node list
- Already circular linked list (should be checked if required)
Advantages of Conversion
- Enables circular traversal
- Useful for round-robin scheduling
- Efficient memory usage
- Simplifies repeated traversal logic
Key Points to Remember
- Only the last node’s next pointer is modified
- No new nodes are created
- Circularity must be maintained carefully
Conclusion
Converting a singly linked list into a circular linked list is a straightforward operation that involves traversing to the last node and linking it back to the head. This operation runs in linear time with constant space and is commonly used in scheduling, buffering, and cyclic data structures.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
