Hey guys,
Well I intend to put up a data structure related puzzle, problem, brain-teaser; whatever you wish to call it everyday from today. This is to keep my dedicated at keeping my skills sharp as I recently discovered that I'm faltering big time. So I shall shart off with a few basic old timer problems and then move on to more tricky problems. I shall provide a solution along with the problem and you can better it and enlighten me. So here goes.
1. How do you find loops in a single link list.
Tortise and Hair solution:
Use two pointers and move the first pointer at double the speed of the seconnd, ie, jump the first pointer by two two nodes while the second pointer moves one node at a time. If at any time the two point at the same node, there's a loop in the link list. If you reach the end of the list, there are no loops in the list.
I'm happy that I started this and hope to stick to my plan for a very long time.
Subscribe to:
Post Comments (Atom)
3 comments:
Hey Sunil,
Solution-2:
1) Traverse thru the linked list. O(n)
2) Maintain a height balanced binary tree
3) Put the address of each node into a height balanced binary tree. Before inserting, see to it that address is not available in the tree. This operation costs O(log n)
This solution is memory consuming as we need to maintain a tree.
If there are large number of nodes in the loop, Tortoise and Hair solution will take time as it can't identify the loop as soon as it starts. But, this solution-2 will identify the looping once it starts.
Again, its a trade-off between memory and time as always.
Always a tradeoff between time and space.
I should include time complexity in all my future posts, and hopefully you will provide a second solution :)
Post a Comment