Subj : Re: How to copy a link list
To   : comp.programming
From : moi
Date : Fri Jul 29 2005 02:44 pm

Alf P. Steinbach wrote:
> * Chinmoy Mukherjee:
> 
>>when the node structure is like
>>
>>struct node {
>>node *next;
>>node *rand; (// random is supposed to point to another node
>>int value;
>>}
> 
> 
> Nitpick: missing semicolon. 
> 
> Since this is not a C++ question but a general programming question I've
> cross-posted this to [comp.programming], with follow-up there.
> 
> Assumption 1. What you have is presumably a singly linked list embedded in a
> general graph, where each node has at most two outgoing connections, and at
> most one node has zero outgoing connections.
> 

That means: following the ->next pointer will walk down the entire list.
But for the ->rand pointer the only restiction is that it is either 
NULL, or it points to one of the list's nodes. No restrictions: loops & 
dead-ends allowed ?

> Assumption 2. Copying the singly linked list structure is also presumably
> easy for you, whereas the 'rand' connections are problematic.
> 
> Assumption 3. And finally, the reason they're problematic is presumably that
> you have some constraints, like (3.1) you want this done in time O(n) or
> thereabouts, where n is the number of nodes, and (3.2) you can't add
> additional fields.
> 

That hurts!

> One way is to first copy only the singly linked list structure, noting in
> the associative container, for each node copied, an association from the
> original's pointer value to the copy's pointer value; then traverse the
> original list and update the 'rand' pointers in the copy.

Some enumeration trick might be feasable. It will be hard for the ->rand
field to temporally encode enough information to "fixup" the ->rand in a
second pass.

Dare I say: maybe an XOR-trick ;-)

*holy thread resurrection, Batman!*

Still thinking,
AvK

.