Circular Linked List Detection

A linked list is given. Write an algorithm that detects whether it's a singly linked list or a circularly linked list.

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