Re: [OT] Linked list fixup [was: Fast DES IP]
From: Kristian Gjøsteen (kristiag+news_at_math.ntnu.no)
Date: 12/09/04
- Next message: Arnaud Carré: "Re: [Lit.] Buffer overruns"
- Previous message: Dag Arne Osvik: "Re: Fast DES IP implementation"
- In reply to: Francois Grieu: "[OT] Linked list fixup [was: Fast DES IP]"
- Next in thread: Phil Carmody: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- Reply: Phil Carmody: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 9 Dec 2004 12:30:08 +0000 (UTC)
Francois Grieu <fgrieu@francenet.fr> wrote:
>We have a non-empty linked list in RAM, of unknown size n,
>and a pointer to the head node. Instead of nicely ending
>with a node having a NULL "next" field, the list is
>"loopy" and the last node in the list has a "next"
>field that points to some unknown node in the list.
>
>Find an O(n) algorithm using O(1) memory that fixes
>the list, changing the "next" field of the last
>element to NULL.
Funny problem. I can solve it using O(n) time and O(log n) memory.
I think this calls for Pollard's kangaroos. So I go to Australia and
pick up my three favourite kangaroos. Fred is the fast one, Sarah and
Sophie are slow. (What are common kangaroo names?)
I send Fred ahead and ride with Sarah until Fred catches up with us.
Then I send Sarah along and record the time r (here I need O(log n)
memory) until she returns.
Now I return to the starting point. I send Sarah along, and when time
r has elapsed, I ride off with Sophie. When Sarah catches up with me, I
mark the place I'm at (again, O(log n) memory), then ride on with Sophie
until the next jump would bring me to the marked place. This is the end.
Finally, I feed the kangaroos and return them to Australia.
-- Kristian Gjøsteen
- Next message: Arnaud Carré: "Re: [Lit.] Buffer overruns"
- Previous message: Dag Arne Osvik: "Re: Fast DES IP implementation"
- In reply to: Francois Grieu: "[OT] Linked list fixup [was: Fast DES IP]"
- Next in thread: Phil Carmody: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- Reply: Phil Carmody: "Re: [OT] Linked list fixup [was: Fast DES IP]"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
