chimaera
BAN USERWhat you need:
two ptrs - a fast ptr and a slow ptr
fast ptr is always one node ahead of the slow ptr
Whenever the slow ptr leaves a node it marks that node - say alters the data such that if data=5 it makes it 5000.
Whenever the fast ptr arrives at a node it checks if the node is marked -- say checks if data/1000 is an integer.
So if your linked list is like this:
O---O----O-----O-----O---O
....|____________________|
Step(1):
f,s
.O---O----O-----O-----O---O
.....|____________________|
Step(2):
.....s....f
.@---O----O-----O-----O---O
.....|____________________|
Step(3):
..........s.....f
.@---@----O-----O-----O---O
.....|____________________|
Step(4):
................s.....f
.@---@----@-----O-----O---O
.....|____________________|
Step(5):
......................s...f
.@---@----@-----@-----O---O
.....|____________________|
Step(6):
.....f....................s
.@---@----@-----@-----@---O
.....|____________________|
Here f checks if @/1000 = O and it is true so we found the last node in the list which is pointed to by 's' which is the slow ptr
Only thing is how to mark the nodes properly. obviously multiplying by 1000 might not work in all cases. Need some unique function.
In the previous comment -- in step(6) the f is on Node:2 and s is on Node:6
- chimaera April 10, 2007