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

Amin A.

Written by

Amin Ariana

A software entrepreneur from San Francisco