Check if a single linked list is circular by going through it only once

Question

I am fresh and I was asked this question in a recent interview that I gave.

The question was --- When looking at each item in a linked list only once, find out if one linked list is circular at any point.

To this I replied that we will save the link of each node when moving the list in another linked list, and for each node in the checked list we will find out if the link exists in the list. I keep links.

The interviewer said that he needed a more streamlined way to solve this problem.

Can someone tell me what would be a more optimized method to solve this problem.

PS: In a circle at any point, I mean this. http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg

Answer 1

The interviewer is looking for whether you know the trick, officially known as the Floyd cycle-finding algorithm , or Tortoise and hare unofficially.

The idea is to advance two pointers in a loop, one moves twice iteration, and the other only once. If a fast-moving pointer approaches a slow backward movement, the list has a loop.

This algorithm detects a loop in O(n) time and O(1) storage. A "slow" pointer goes through the list no more than once, so it’s fair to say that the algorithm finds the answer in one round.

In my opinion, this algorithm makes a bad question for the interview, because it is difficult to find on the spot if you do not know it ahead of time. At the same time, this is not an algorithm that is used so widely that everyone should know about it, making me wonder why someone asked about this in an interview.

Answer 2

I doubt the interviewer's goal was to find out if you know the Floyd cycle-find algorithm. The goal of such a question would be to understand whether you understand the concepts of data structures such as lists, binary trees, and hashes.

The main problem with your answer is that the algorithm you provided has complexity O (n ^ 2), i.e. O (n) to move the original list * O (n) to check if each node exists in the second list, by every iteration.

When the interviewer asked you to optimize your answer, you could suggest replacing the second linked list with a different data structure that provides a quick search than O (n). For example, a binary tree has O (logn) search complexity, and a hash has O (1) search complexity (not always, but this is a generally accepted assumption), which is much faster than using a second linked list that has O (n) search complexity.

So the O (n) solution should replace your second linked list with a hash (i.e. HashMap, HashSet, etc.).

Of course, the Floyd cycle-find algorithm is a more elegant solution to this problem, since it has better memory complexity (i.e. there is no need to store the visited nodes in memory).

Answer 3

An even more efficient approach would be to have one iterator and check for a node pointing to zero ... This approach should be twice as efficient as the above approach.

Answer 4

 tempNode = list; while((tempNode->next != list) && (tempNode->next != NULL)) tempNode = tempNode->next; if(tempNode->next == list) //list is circular if(tempNode->next == NULL) //list is not circular Above two conditions can be addressed in while loop also