Scene 19 of Graph Traversals in Core Technical Interview Questions for Software Engineers
By Amin Ariana — August 2006
Problem Statement
Given a pointer to a potentially large linked list, write an algorithm to detect whether it is a singly linked list or a circularly linked list.
Note: Given the size of the linked list, you cannot rely on having much memory left over once it is loaded. Your solution therefore must not need a lot of additional space.
Evaluation
- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity, and is it efficient? (25%)
- Did you write it using constant space? (25%)
Solution
Hint 1
Don't write an algorithm to find the NULL end of the singly linked list. It will never terminate for a circularly linked list, but you do need it to terminate to return the answer.
Hint 2
The best solution I have seen for this declares two pointers, both starting at the given origin. One pointer traverses one node at a time while the other traverses two nodes at a time. If they eventually collide, their shared path must be a loop.
References
Microsoft interview question