Linked List Puzzle

[Sidoh]

This is an interesting problem we discussed earlier today.  It assumes that you have a pretty good idea of what linked lists are, how they work and how elementary operations with them are developed (ie, iteration).  Feel free to ask questions if you don't understand something.

Without further adieu, here's the problem.

You suspect that a given linked list is "corrupted."  By corrupted, I mean that the a node in the list points back to an earlier node, creating a loop.  Here's a diagram to demonstrate the problem:



Now, this is a pretty obvious problem that doesn't take much effort to conceptualize, but this puzzle makes things a bit more difficult.  You are only given a pointer to the first node in the list and that's it.  Your task is to find a way to tell if a given list is corrupted with no additional information concerning the list.  You don't know its size or where it is "supposed" to end.

There are a couple of fairly obvious solutions and there are at least two clever solutions that I know of, for your information.

[Joe]

Na boivbhf nafjre vf gb trg gur cbvagre bs rnpu abqr orsber tbvat gb gur arkg, naq juvpu rnpu bar frr vs lbh'ir orra gurer orsber. Gur svefg gung frgf bss guvf pbaqvgvba vf gur bar gung gur ybbc fgnegf ng, naq gur bar orsber vg vf gur bar gung lbh'er whzcvat sebz.

Nabgure boivbhf bar vf gb frr juvpu bar vf gryyvat lbh gb whzc, ohg gung'f ab sha.

[Sidoh]

Yeah, that's the really obvious answer.  It's also the most inefficient.

I don't know what you mean by "telling you to jump."  I'm quite sure that makes no sense.

[Ender]

Guvf qbrfa'g frrz irel pyrire (naq vg fbeg bs frrzf yvxr purngvat), ohg vg vf fbzrjung rssvpvrag, fb V'yy cbfg vg.

Tvir rnpu abqr n choyvp vfErsreraprq obbyrna. Rirel gvzr lbh vgrengr lbh jvyy purpx gb frr vs gur arkg abqr'f vfErsreraprq obbyrna vf frg gb gehr. Vs vg'f abg, lbh frg vg gb gehr nsgre lbh vgrengr cnfg vg. Vs vg vf frg gb gehr, gura lbh xabj gurer'f n ybbc.

V qba'g xabj jurgure Wbr tnir guvf fbyhgvba be gur B(a) frnepu guebhtu gur yvfg bs cnfg cbvagref... sbhaq vg n ovg uneq gb ernq... ohg bu jryy.

[Ender]

Nabgure jnl, juvpu vf ernyyl whfg n erivfvba bs gur ynfg cbfg va beqre gb znxr vg abg frrz yvxr "purngvat" (guvf jnl lbh qba'g unir gb zbqvsl gur abqr pynff), vf:

Lbh xrrc n Znc jurer gur cbvagref ner gur xrlf naq gur inyhrf ner obbyrnaf. Orsber lbh vgrengr n abqr lbh purpx gb frr jung inyhr gur abqr vf znccrq gb. Abqrf fubhyq or znccrq gb "snyfr" ol qrsnhyg. Fb vs vg'f snyfr, gur abqr unf abg orra ersreraprq lrg. Vs vg'f gehr, gura gur abqr unf orra ersreraprq nyernql, naq gurer'f n ybbc.

Gur naablvat guvat vf gung guvf vf B(a/2), ohg V oryvrir Wbr'f jnl vf B(a^2).

Gurer ner fbzr bgure purrfl jnlf V pna guvax bs qbvat guvf. Yvxr unfuvat rnpu ersrerapr naq fgbevat vg va bar ovt unfu naq gura NAQvat gung ovt unfu jvgu gur arkg abqr'f unfu. Ohg gung'f purrfl ;-)

[Sidoh]

I should also mention that you can't change the structure of a node.

Yeah, Hash Tables would be more efficient.

I'll post one of the solutions later today (I wrote a working implementation of it in C last night).

[Sidoh]

Warning! Answer below.  If you want to work on it yourself, don't read it!


Okay, so here's one of the two clever solutions:

Starting at the front (head) of the list, you reverse all of the pointers.  So, for example, in the first iteration of this procedure, you'd buffer the head pointer, move to the next pointer.

Now, check if the current node's next pointer is the head pointer.

If it is, then you know you've traversed a loop and ended up back at the beginning of the list.  You can therefore conclude that the list is corrupted.

If not, create another buffer pointing to the current pointer and advance the current pointer to the next one. Then set the buffer pointer's next pointer to the aforementioned buffer.

Repeat this until current -> next is NULL.

Here's a diagram (poorly) illustrating what's going on:
http://sidoh.dark-wire.net/upload/viewitem.php?id=123

Here's a quick implementation of this procedure I whipped up in C last night.
http://www.christophermullins.net/index.php/codebin/viewcode/10/?window=1

Here's all of the code batched together:
http://www.christophermullins.net/index.php/codebin/viewproject/3

Here's what the code looks like when ran:
mullins@antero:~/src/c/ll$ make; ./ll
gcc linked_list.c -o ll
List generated: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
Reversed list (starting at 25 -> 24 -> ...): [25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
Reversed list (starting at 1 -> 2 -> 3 -> ...): [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
Attempting the reverse-pointer corruption test: 1
Corrupting list...
Attempting the reverse-pointer corruption test: 0

I'll post the other solution later.