linked list with cycle structure
david at hlacik.eu
Thu Jan 8 23:24:21 CET 2009
well i am able to find a loop in a list using two iterators.One
iterator runs "two times faster than the other", and if he encounters
the first, it means that there is a loop.
the algorithm would generate:
start - 1,2
iteration 1- 2, 4
iteration 2- 3, 6
iteration 3- 4, 8
iteration 4- 5, 5 ( match)
But how can this help me with counting list elements? :(
On Thu, Jan 8, 2009 at 5:48 PM, Diez B. Roggisch <deets at nospam.web.de> wrote:
> David Hláčik wrote:
> > Hi,
> > so okay, i will create a helping set, where i will be adding elements
> > ID, when element ID will be allready in my helping set i will stop and
> > count number of elements in helping set. This is how long my cycled
> > linked list is.
> > But what if i have another condition , and that is *i can use only
> > helping memory with constant size* ? This means i am not able to
> > create any set and adding elements there. I need to have a constant
> > size variables . This is complication a complication for me.
> This isn't to hard - think about what you are really interested in - knowing
> if *all* other elements are already counted, or a specific one? You can get
> away with only one, to detect the cycle and abort.
More information about the Python-list