linked list with cycle structure

David Hláčik david at hlacik.eu
Thu Jan 8 23:24:21 CET 2009


Hi,

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.

Example :
1,2,3,4,5,6,7,8,9,5
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? :(

Thanks,

D.

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.
>
> Diez
> --
> http://mail.python.org/mailman/listinfo/python-list


More information about the Python-list mailing list