Is list singly-circularly-linked list problem

Hi, it’s my first post on the blog ever! :-)

To not bore you telling how excited I am having my own blog I would like to give you some food for thought. You should be also warned: on this blog it’s going to be much more this kind of stuff as I’m math student of MIMUW. Yes, that famous and unbeatable university ;-)

Ok, let’s move to the problem that my colleague (PaweĊ‚) told me about today. There is an singly-linked list and we are given one of the nodes it consists of.
The problem: how to determine in O(n) time and O(1) memory if this list is singly-circularly-linked list or not. In other words: does the list have a cycle? O(n) means that your algorithm must be linear when it comes to the number of elementary operations and can modify only constant amount of memory. That means you cannot mark particular node if it was visited or not.

In order to avoid confusion I’ve created drawing illustrating valid list:list.png

Ok, I promise to not use OpenOffice.org Draw and produce nicer image next time.

About these ads

8 Responses to “Is list singly-circularly-linked list problem”

  1. Antonio Fiol Says:

    If the length (qty of nodes) of the list is bounded (with a known bound), even if the actual length is not known, I can think of an easy solution. But I guess the problem lies with unbounded length lists. :-(

  2. Grzegorz Kossakowski Says:

    Yes, you are right – we only know (what is obvious) that the number of nodes in the list is finite. There is no known bound for length.

    Problem formulated that way is also easy. I’m going to post the solution this week so hurry up! There is not that much time left to shine. ;)

  3. Solution for singly-circularly-linked problem « Reflecting on the vicissitudes Says:

    [...] for singly-circularly-linked problem I promised to post a solution for the problem I set earlier. Now it’s time to keep the [...]

  4. Roman Says:

    ptr1=ptr2=list.first

    while(true)
    {
    if(ptr1.next != null && ptr2.next!=null)
    {
    ptr1=ptr1.next;
    ptr2=ptr1.next.next;
    }
    else
    // is singly-linked list

    if(ptr1==ptr2)
    // is singly-circularly-linked list
    }

  5. sa Says:

    grt.!

  6. shlomi Says:

    But it looks like an endless loop !?

  7. Grzegorz Kossakowski Says:

    shloami: take a look at my solution that I posted here:
    http://reflectingonthevicissitudes.wordpress.com/2007/06/10/solution-for-singly-circularly-linked-problem/
    (it’s more or less the same as Roman’s)

  8. shlomi Says:

    Thank you, Grzegorz, for the clarification – simple, & brilliant…

    Another question, please : How can I point to the first element of the cycle ?
    Shlomi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: