Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: In-Person
There are several approach to check whether link list is circular or not:-
1st Approach :
Take a flag bit at each node and make it zero initially. While visiting each node make the flag bit as one if it is zero. If already flag bit found as one then loop exist that is circular list.
If somebody ask how we can take the flag bit at each node by own then you just give answer as while doing programming we always take some extra bit for future purpose.so we make it as flag bit. If they also not satisfied then just say i will take resize function to increase the size of node and then we use the flag bit. Time complexity= O(n).
2nd Approach :
Take an array. Store the 1st node next address and go to second node. while go to next node just check whether next address is already stored in array........and so on .Time complexity =O(square of n)
3rd approach:
start with two pointer from starting point of the list and increase 1st pointer by one and 2nd by two if the pointer meet on same point then the list is circular list else not.
Time complexity = O(n). This is the best algorithm. Its time complexity is asymptotically order of n but actually on an average it is n/2.
Start from a given node and traverse the linked list. Validate for null or start node point condition while traversing the linkedlist . In case we find node->next = null at any time then LL is not circular in nature. In case we encounter starting node address again then it means it is circular LL.
Thanks,
start two pointer from starting point of the list and increase 1st pointer by one and 2nd by two if they pointer meet on same point than the list is circular list else not.
- Amnish yadav December 19, 2014