Symphony Services Interview Question
Production EngineersCountry: India
Interview Type: In-Person
If you not able to detect the start and end of the circular linked list in a traversal, it will result in looping.
To avoid this detect the start and the end of the linked list. It can be done by,
Way -1
Have an temp variable pointing to your starting location. So when you iterate everytime check for the equality.
Way -2
Have two temp pointers. Pointers moves one location for every iteration and pointer b moves two locations for one iteration. The point where and b meets together is end of the linked list.
Note : Pointer B will have to be iterated twice.
Tortoise and Hare algorithm
- lklein September 16, 2011