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
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