Check If Circular Linked List

Problem

Given head, the head of a singly linked list, find if the linked list is circular or not. A linked list is called circular if it not NULL terminated and all nodes are connected in the form of a cycle. An empty linked list is considered as circular.

Note: The linked list does not contains any inner loop.

Examples:

Example 1:

Input:
LinkedList: 1->2->3->4->5 (the first and last node is connected, i.e. 5 --> 1)
Output: 1

Example 2:

Input:
LinkedList: 2->4->6->7->5->1
Output: 0

Your task:

The task is to complete the function isCircular() which checks if the given linked list is circular or not. It should return true or false accordingly. (the driver code prints 1 if the returned values is true, otherwise 0)

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 <=$Number of nodes$<= 100$

Solution

Python

def isCircular(head):
    if head is None: 
        return False
    slow = head 
    fast = head.next
    while fast is not None and fast.next is not None: 
        if slow == fast: 
            return True
        slow = slow.next
        fast = fast.next.next
    return False

Java

boolean isCircular(Node head) {
    if (head == null) {
        return false;
    }
    Node slow = head;
    Node fast = head.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;	
}

C++

bool isCircular(Node *head) {
    if (head == NULL) {
        return false;
    }
    Node* slow = head;
    Node* fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
        if (slow == fast) {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

C

bool isCircular(struct Node *head){
    if (head == NULL) {
        return false;
    }
    struct Node *slow = head;
    struct Node *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) {
          return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$