Is it a Circular Linked List ? — Asked in Amazon in Microsoft, MAQ Software and SAP Labs Interview

Problem Statement :

You are given a Singly Linked List of integers. You have to find if the given linked list is circular or not.

A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element. This means that circular linked list is similar to the single linked list except that the last node points to the first node in the list.

Sample Input:

1 2 3 4 -1

Sample Output:

True

Approach :

Iterative Approach

The idea is to store the head node and traverse the list. If we reach the end (NULL), then the given linked list is not circular, else if we reach the head again, then the linked list is circular.

Algorithm

Take a pointer ‘cur’, which initially points to the head node. Move the pointer ‘cur’ to the next node until you find one of the following nodes

• NULL: represents that the given linked list is not circular.
• head: represents that the given linked list is circular.

Time Complexity: O(N)
Space complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.