## Introduction

The **circular linked list** is also a type of the **singly linked list**, the sole difference being that its last node points to the first node, so its link part holds the address of the first node. While the linked part of the last node of the singly linked list always contains a NULL value. A circular linked list can be traversed in any direction, either clockwise or anticlockwise, as it has no starting or ending node. (See, Traversal of a Circular Linked List)

A singly linked list looks like this:

While a circular linked list looks like this:

Circular linked lists are useful in repeatedly going over the list and are also used to implement advanced data structures.

This blog will discuss how to convert a singly linked list to a circular linked list.

Recommended Topic, __Floyds Algorithm__ and __Rabin Karp Algorithm__

## Algorithm

The algorithm is quite simple:

- Traverse the linked list and find the last node.
- If the node is the last node and points to NULL, make it point to the head node.
- The singly linked list has now been converted into the circular linked list.

### Implementation

```
// C++ program to convert a singly linked list to a circular linked list.
#include <iostream>
using namespace std;
// 'NODE' class to store linked list nodes.
class Node
{
public:
int data;
Node *next;
// Constructor to create a node with given data.
Node(int data)
{
this->data = data;
next = NULL;
}
};
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
// 'HEAD' pointer to store the address of the first node.
Node *head;
public:
LinkedList()
{
head = NULL;
}
// To print the elements of the circular linked list.
void printLinkedList()
{
Node *current = head;
// Displaying the nodes of the linked list.
while (current->next != head)
{
cout << current->data << " ";
current = current->next;
}
cout << current->data << " ";
}
// Function to insert nodes in the linked list.
void insert(int data)
{
/* If linked list is empty, create a new node
and direct the 'HEAD' node to the newly created node.
*/
if (head == NULL)
{
head = new Node(data);
return;
}
// Else traverse the linked list until the end of the list is encountered.
Node *current = head;
while (current->next)
{
current = current->next;
}
// Create and insert a new node at the end of the linked list.
current->next = new Node(data);
}
// Function to convert a singly linked list to a circular linked list.
void circular()
{
// Declaring a node variable and assigning the head node to it.
Node *current = head;
// If the next node to the current node is not NULL, the head points to the next node.
while (current->next != NULL)
current = current->next;
// If the next node to the current node is NULL, the head points to the first node.
current->next = head;
head = current;
}
};
int main()
{
int n, data;
// Taking user input.
cout << "Enter the size of the linked list: ";
cin >> n;
LinkedList *givenList = new LinkedList();
cout << "Enter the values of the nodes: \n";
for (int i = 0; i < n; i++)
{
cin >> data;
givenList->insert(data);
}
// Call the function to convert the singly linked list to a circular linked list and print it.
givenList->circular();
printf("The circular linked list is: \n");
givenList->printLinkedList();
return 0;
}
```

**Input**

```
Enter the size of the linked list: 6
Enter the values of the nodes:
8 6 14 19 23 10
```

**Output**

```
The circular linked list is:
10 8 6 14 19 23
```

### Complexities

**Time Complexity**

O(N), where N is the size of the linked list.

Since we are traversing the entire linked list, the time complexity is given by O(N).

**Space Complexity**

The space complexity is O(1)

The space complexity is constant as we are not using extra space except for variables.

Note: If we maintain the tail pointer along with the head pointer in our singly linked list then it can be converted to a circular linked list in O(1) time by updating the next pointer of the tail with the head.

Also read - __Merge sort in linked list__

### Frequently Asked Questions

### What is the major difference between a Singly-Linked List and a Circular Linked List?

A Singly-Linked List has a null pointer after the last node meaning it has an end and a beginning whereas a Circular Linked List much like a circle has no beginning and no end. Any of the nodes could be considered as the starting or ending nodes.

### What is the time complexity of inserting an element in a Circular Linked List?

The time complexity of the insertion of an element in a Circular Linked List is O(N) where N is the size of the Linked List