Who owns a character?

Transcript note: recovered from UsenetArchives. Email addresses and personal contact URLs are redacted; spelling, punctuation and the remaining text are preserved.

stevet — Nov 18, 1998 19:00 UTC

Jon A. Lambert  wrote:
›
▶

On 18 Nov 1998 19:08:27 GMT, J C Lawrence said:
(8 lines)
› On 18 Nov 1998 19:08:27 GMT, J C Lawrence said:
››
››  Given a singly linked list of objects and a pointer to the first
›› node on the list, what is the most efficient (time __and__
›› resources) algorithm you can come up with to detect if the list is
›› circular?
››

› Hmmm, how about walking the list copying the pointers into an STL set
› container.  As soon as you hit a "bad" insert, you have the answer.
› I think it's fairly inexpensive.  :)

That isn't bad.  But it seems excessive if all you are doing is checking to
see if it is circular.  I was actually asked this question once, and came up
with this solution:

Take pointer A and move it two slots down the list, take pointer B and move it
one slot.  If pointer A is ever equal to pointer B (on either of the two slots
in each move) then the list loops, if not then it doesn't.  n time right?  And
only a few pointer assignments and 1 comparison per node.

-Steve

Signature
  Stephen C. Thompson
  [email redacted]

[personal URL redacted]
  Dark Pawns:  mud.darkrune.org 4000