3 Apr
2006
3 Apr
'06
11:13 a.m.
It was thus said that the Great Jim Battle once stated:
Ah, this is funny. I was once asked the following trick question. Say
you have a singly linked list. This list might be a simple chain, or it
might loop on itself. For reasons that can't be explained, you are
allowed to use only two memory locations to decide if the list loops or
not. After a couple questions to clarify, it was allowed that speed
wasn't important and that the size of an integer and a pointer were the
same. A 0 pointer marks the end of the list.
[ snip ]
The clever answer is to have two pointers. At each
step of the
algorithm, one pointer advances two steps and the other pointer advances
three steps (any relatively prime pair of increments would work). After
the pointers are advanced, check if they are the same. If there is a
loop, eventually the two pointers will coincide, even if they have to
race around the loop a few times before their phases align. Never mind
the fact that actually coding it is a bit of a mess since at each of the
places where the pointers must be advanced, each intermediate step must
be checked for the end of list condition.
Gee, I think I could do that in one memory location---cache the value of
the first pointer. Keep following the list, checking each address against
the cached value. If you hit 0, it terminates, otherwise if the address
matches the cached value, you have a loop. The above method is cleverness
(not) for cleverness sake.
-spc (Or are you *forced* to use two memory locations?)