Subj : Re: How to copy a link list
To   : comp.lang.c++,comp.programming
From : alfps
Date : Mon Jul 25 2005 09:36 am

* 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.

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.

With no limitations on the graph structure other than what's mentioned above
it seems your only option is to use an associative container.  Current
standard C++ doesn't have hash tables in the standard library, but they're
common in actual implementations.  If you want to only use standard
containers a std::map will do the job, but then with total time O(n log n)
(cirka).

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.

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

.