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 pseudocode 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
Recommended reading

Graph Cycle Detection
You have a directed connected graph. Write an algorithm that detects any cycle, if one exists, and returns a list of its nodes.

Find the middle node of a Linked List
Given a Singly Linked List, write an algorithm to find the middle node. You may not use more than one loop of any kind.

Reverse a Singly Linked List
Implement the algorithm to reverse a singly linked list.

Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.
 Author
 Amin Ariana
 Published
 August 2006