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