Brain teaser

A tricky little problem. I recently encountered it (again) at an interview. Although not complex and very easy to express, I found few people that solved it.

It goes like this: you're given a single-linked list (its head). In O(1) (constant) space complexity you have to determine if the list is circular or not. This constraint basically says that you can't use a variable for each list element (to remember if you've been there before for example).

NOTE: a circular list is also one of the type 1->2->3->4->2 - a portion of the list being outside the loop.

Comments

[Laurence Vanhelsuwe]

Given that you pin the space dimension, you apparently are allowing infinite time to pass to obtain the answer. So my tongue-in-cheek solution would be to just time the linear scanning of the list, and if the scan returns (ie reaches the end), then there's no loop involved. If you had a really zipping fast scanner, you could roughly calculate how long it would take to scan thru a list that filled all available RAM, then just launch the scanner with a timeout/kill mechanism. Wasteful, but it would work, especially if you could ensure that your process does not get interrupted or slowed down in any way.

[Paul Martin]

Although the solution would most likely work (slowly) in practice due to the RAM size limit, it's not the sound algorithmical solution that a programmer would prefer.
Still looking for ideas ;)

[sergiogiogio]

Suppose you iterate the list:
- you know the list is not circular if you reach the end
- you know the list is circular if you reach a node you reached earlier.

Here's my suggestion: as you iterate, remember only one node:
- first remember only node 0
- then remember only node 10 (as you iterate over it)
- then remember only node 21 (as you iterate over it)
- then remember only node 32 (as you iterate over it)
- then remember only node 43 (as you iterate over it)
- etc.
Note that the "gap" between the nodes you remember regularly increases (10, then 11, then 12, etc).

During the iteration:
- if you reach the same node you currently remember, then the list is circular.
- if you reach the end of the list then the list is not circular.

This works because the loop part has a fixed number of nodes "N", and when you are in the loop and the "gap" >= "N", then you will reach the node you remembered last. This is the reason why the gap increases regularly. If you are not in the loop then you keep on moving forward until reaching the loop. If there is no loop then you reach the end.

[Paul Martin]

Sergio, good job
You have a valid solution!

Let me show another more time-efficient approach: iterate the list twice at the same time and make one iteration visit each node and the second skip every other node (you can imagine it as two runners on a track, one having double speed).

If you reach the list end, it's not circular; if you at any moment visit the same node with the two iterations, you have a cycle.

Paul