We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Find length of Circular Linked List
Last updated:
The length of a circular linked list is the number of nodes in the ring. It is counted by walking once around the ring from the head.
The only difference from a linear list is the stop condition. The last node does not point to null; it points back to the head. So the count stops when the walk returns to the head, and a do-while loop makes sure the head itself is counted. An empty list (head == null) has length 0.
Example: the ring in the diagram has three nodes, so its length is 3.
Example: Find the length of Circular Linked List in Java
FindLengthInCLL.java
// Class representing a node in a circular linked list
class Node {
public int data; // Store value of the node
public Node next; // Store address of the next node
// Constructor to initialize a node
public Node(int data) {
this.data = data;
this.next = null;
}
}
// Java program to find the length of a circular linked list
public class FindLengthInCLL {
// Function to find length of circular linked list
static void findLength(Node head) {
int length = 0;
if (head != null) {
Node node = head;
do {
node = node.next;
length++;
} while (node != head);
}
System.out.println("Length of Circular Linked List is: " + length);
}
public static void main(String[] args) {
// Create a circular linked list
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
head.next.next.next.next.next = head;
// Find and print the length of a Circular Linked List
findLength(head);
}
}
Output
Length of Circular Linked List is: 5
Time Complexity: O(n), where n is the number of nodes; each node is visited once.
Extra Space: O(1)
Frequently Asked Questions (FAQ)
Q1. How do you find the length of a circular linked list?
LengthCircular.java
public class LengthCircular {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
static int length(Node head) {
if (head == null) {
return 0;
}
int count = 0;
Node current = head;
do {
count++;
current = current.next;
} while (current != head);
return count;
}
}
Q2. Why can you not use while (current != null) to count the nodes?
A circular list has no null at the end, so that loop never stops. The count must stop when the traversal comes back to the head.
Q3. What is the length of a circular linked list with one node?
1. The node points to itself, and the do-while loop counts it once before returning to the head.
Q4. How do you find the length of a circular linked list recursively?
LengthRecursive.java
public class LengthRecursive {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
static int length(Node current, Node head) {
if (current == null) {
return 0; // empty list
}
if (current.next == head) {
return 1;
}
return 1 + length(current.next, head);
}
// Call: head == null ? 0 : length(head, head)
}
Q5. How can you get the length of a circular linked list in O(1)?
Keep a size counter in the list class and update it whenever a node is inserted or deleted. Then reading the length is O(1).
Q6. How do you find the length of a loop in a linear list that ends in a cycle?
Use Floyd's algorithm to find a node inside the loop, then walk around the loop once and count:
LoopLength.java
public class LoopLength {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
static int loopLength(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
int length = 1;
for (Node n = slow.next; n != slow; n = n.next) {
length++;
}
return length;
}
}
return 0; // no loop
}
}
Q7. What is the time and space complexity of finding the length?
Iterative counting is O(n) time and O(1) space. The recursive version uses O(n) stack space.
Q8. How do you check whether a circular linked list has an even number of nodes?
IsEven.java
public class IsEven {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
static boolean hasEvenLength(Node head) {
if (head == null) {
return true;
}
boolean even = true;
Node current = head;
do {
even = !even;
current = current.next;
} while (current != head);
return even;
}
}
Q9. Why is knowing the length useful in a circular list?
It lets you convert a large step count into a small one. For example, moving k steps around a ring of length n lands on the same node as moving k % n steps, which avoids walking many full rounds.
Q10. What is the length of an empty circular linked list, and how should it be handled?
The length is 0. Check head == null before the do-while loop; otherwise the loop would try to read head.next and throw a NullPointerException.