Riverbed Interview Question Software Engineer / Developers
0of 0 votesHow to check a loop in a link list?
Country: United States
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
2nd way is to use hashtable, not good way as Tortoise and Hare Algorithm
Create hashtable and start pulling item from linkedList one-by-one and put it inside hashtabe. Before putting it check if it is exist in hashtable, if yes, then you are done. You came to the object where cycle started.
Comment hidden because of low score. Click to expand.
0
of 0 votes
This does not take care of the case where the list might containt duplicate elements...
consider the case: 1-> 2->3 -> 4 -> 3' (a new 3)
this list does not contain a loop
consider the case: 1-> 2-> 3 -> 4 -> 3' (new 3) -> 5-> 3 (first 3)
this list does contain a loop.
Comment hidden because of low score. Click to expand.
You can use the Cycle Detection Algorithm (in particular, I like the Tortoise and Hare Algorithm). Look it up on Wikipedia.
- JustCoding September 27, 2012The basic idea is to have 2 pointers: one slow and one fast... both start at the head of the list. The slow pointer moves one step at a time and the fast pointer moves 2 steps at a time. If they meet at any time ie.,e if slow == fast, there is a loop in the list...