Check if a linked list is Circular Linked List

Problem: Given a singly linked list, find if the linked list is circular or not.

Circular Linked List: A linked list is called circular if it not NULL terminated and all nodes are connected in the form of a cycle.

For example:

Input:

Output: Yes

Input:

Output: No

Method 1: Maintain two pointers, fast and slow is used while iterating over linked list. Fast pointer moves two nodes in each iteration, while slow pointer moves to one node. If linked list contains loop or cycle than both fast and slow pointer will meet at some point during iteration. If they don't meet and fast or slow will point to null, then linked list is not cyclic and it doesn't contain any loop.

Below is the exact algorithm:

1. Use two pointers fast and slow 
2. Move fast two nodes and slow one node in each iteration 
3. If fast and slow meet then linked list contains cycle 
4. if fast points to null or fast.next points to null then linked list is not cyclic

This algorithm is also known as Floyd’s cycle finding algorithm and popularly known as tortoise and hare algorithm to find cycles in linked list.

bool findCircular(Node *head)
{ 
    /* initial two pointers */
    Node fast = head; 
    Node slow = head;

    while(fast != null && fast.next != null)
    {
        /* advance fast pointer twice as slow pointer */
        fast = fast.next.next; 
        slow = slow.next; 
        if(fast == slow )
        { 
            return true; 
        } 
    } 
    return false; 
}

Time Complexity: O(n)