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.
Ok, I promise to not use OpenOffice.org Draw and produce nicer image next time.