Skip to main content

Check if a linked list is Circular Linked List

The problem involves checking whether a given singly linked list is a circular linked list or not. In a circular linked list, the last node's next pointer points back to the first node, creating a closed loop.

Problem Statement

Given a singly linked list, we need to determine whether it's a circular linked list or not.

Example

Consider the following linked list: 1 -> 2 -> 3 -> 4 -> 5. This is not a circular linked list because the last node's next pointer is NULL. However, if we connect the last node's next pointer to the first node, it becomes a circular linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 1.

Idea to Solve the Problem

Length of Loop in linked listcheck linked list is circular or not

To check if a linked list is a circular linked list, we can traverse the list while checking if the next pointer of the current node ever becomes NULL. If we encounter a NULL next pointer, it means the list is not circular. If we encounter a node whose next pointer points back to a previously visited node, it indicates that the list is circular.

Pseudocode

Here's the pseudocode to check if a linked list is circular:

function isCircular(linkedList):
    if linkedList.head is NULL:
        return 0
    
    temp = linkedList.head
    while temp is not NULL:
        temp = temp.next
        if temp is linkedList.head:
            return 1
        if temp is NULL:
            return 0

Algorithm Explanation

  1. Check if the linked list is empty. If it's empty, return 0 (not circular).
  2. Initialize temp to the head of the linked list.
  3. Traverse the linked list using the temp pointer. If temp becomes equal to the head again, return 1 (circular).
  4. If temp becomes NULL, return 0 (not circular).

Code Solution

Time Complexity

The time complexity of checking whether a linked list is circular or not is O(n), where n is the number of nodes in the linked list. This is because we need to traverse the entire list to determine its circular nature.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment