What is difference between C++ Destructor and Java Finalize method ?
February 19, 2010
February 8, 2010
Detecting A cycle in Singly linked List
http://www.siafoo.net/algorithm/10
http://www.siafoo.net/algorithm/11
How do you determine if your singly-linked list has a cycle? In the late 1960s, Robert W. Floyd invented an algorithm that worked in linear (O(N)) time. It is also called Floyd’s cycle detection algorithm.
The easiest solution to the cycle detection problem is to run through the list, keeping track of which nodes you visit, and on each node check to see if it is the same as any of the previous nodes. It’s pretty obvious that this runs in quadratic (O(N^2)) time… not very efficient, and actually more complicated than this one.
The Tortoise and the Hare is possibly the most famous cycle detection algorithm, and is surprisingly straightforward. The Tortoise and the Hare are both pointers, and both start at the top of the list. For each iteration, the Tortoise takes one step and the Hare takes two. If there is a loop, the hare will go around that loop (possibly more than once) and eventually meet up with the turtle when the turtle gets into the loop. If there is no loop, the hare will get to the end of the list without meeting up with the turtle.
Why can’t you just let the hare go by itself? If there was a loop, it would just go forever; the turtle ensues you will only take n steps at most.
For a somewhat more efficient algorithm, check out Brent’s Cycle Detection Algorithm (The Teleporting Turtle).
How do you determine if your singly-linked list has a cycle? In 1980, Brent invented an algorithm that not only worked in linear time, but required less stepping than Floyd’s Tortoise and the Hare algorithm (however it is slightly more complex). Although stepping through a ‘regular’ linked list is computationally easy, these algorithms are also used for factorization and pseudorandom number generators, linked lists are implicit and finding the next member is computationally difficult.
Brent’s algorithm features a moving rabbit and a stationary, then teleporting, turtle. Both turtle and rabbit start at the top of the list. The rabbit takes one step per iteration. If it is then at the same position as the stationary turtle, there is obviously a loop. If it reaches the end of the list, there is no loop.
Of course, this by itself will take infinite time if there is a loop. So every once in a while, we teleport the turtle to the rabbit’s position, and let the rabbit continue moving. We start out waiting just 2 steps before teleportation, and we double that each time we move the turtle.
Why move the turtle at all? Well, the loop might not include the entire list; if a rabbit gets stuck in a loop further down, without the turtle, it will go forever. Why take twice as long each time? Eventually, the length of time between teleportations will become longer than the size of the loop, and the turtle will be there waiting for the rabbit when it gets back.
Note that like Floyd’s Tortoise and Hare algorithm, this one runs in O(N). However you’re doing less stepping than with Floyd’s (in fact the upper bound for steps is the number you would do with Floyd’s algorithm). According to Brent’s research, his algorithm is 24-36% faster on average for implicit linked list algorithms.
Algorithm for converting a string to an integer value.
Hints:
1. Check that each character is a numeric character. Take into consideration the base in which the conversion is sought.
2. Identify the character in ASCII and convert it to numeral ’1′ -> 1
3. Iterate over string and Multiply by the appropriate base and add it to temp to find the value of the number.
Also take care that number is -ve
