when the node structure is like

struct node {
node *next;
node *rand; (// random is supposed to point to another
node
int value;
}

"Chinmoy Mukherjee" <a17199@motorola.com> wrote in message
news:42E47BF9.B40ECD3A@motorola.com...[color=blue]
> when the node structure is like
>
> struct node {
> node *next;
> node *rand; (// random is supposed to point to another
> node
> int value;
> }[/color]


Traverse list, create copy of each node, link nodes correctly
together.

hth
--
jb

(reply address in rot13, unscramble first)

Chinmoy Mukherjee sade:[color=blue]
> when the node structure is like
>
> struct node {
> node *next;
> node *rand; (// random is supposed to point to another
> node
> int value;
> }
>[/color]

node * node::copy()
{
COPY THIS TO TEMP
IF NEXT THEN
LINK TEMP TO CALL NEXT COPY
ENDIF
RETURN TEMP
}

Tobias
--
IMPORTANT: The contents of this email and attachments are confidential
and may be subject to legal privilege and/or protected by copyright.
Copying or communicating any part of it to others is prohibited and may
be unlawful.

If that node *rand really points to a random other node you need to add
in an unique identifier (uid) in each node for copying purposes.
Then you a have two/three step copy process.
First create the new nodes with value and uid copied & next containing
a pointer to a new node.
Then traverse the newly created list adding the rand values.
pseudocode
dummy = first copied node
while dummy->uid != original node->rand->uid dummy =
dummy->next;
copied node->rand = dummy;

Third step is optional, assigning unique uids to the copied nodes.

* Chinmoy Mukherjee:[color=blue]
> when the node structure is like
>
> struct node {
> node *next;
> node *rand; (// random is supposed to point to another node
> int value;
> }[/color]

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?

The cleanest way:
Provide iterators, use STL algorithms

Ben
[color=blue]
> when the node structure is like
>
> struct node {
> node *next;
> node *rand; (// random is supposed to point to another
> node
> int value;
> }
>[/color]

Thanks Jakob.
But how to I remember the rand poniters of each node
the idea is to retain the strcuture

For example, assume we create a link list of size 5

now assign node0->rand = node4
node1->rand = node0
node2->rand = node3
node3->rand = node2

Now question is how do I copy the link list to
another link list so that the overall structure is retained.
Regards,
Chinmoy

Jakob Bieling wrote:
[color=blue]
> "Chinmoy Mukherjee" <a17199@motorola.com> wrote in message
> news:42E47BF9.B40ECD3A@motorola.com...[color=green]
> > when the node structure is like
> >
> > struct node {
> > node *next;
> > node *rand; (// random is supposed to point to another
> > node
> > int value;
> > }[/color]
>
> Traverse list, create copy of each node, link nodes correctly
> together.
>
> hth
> --
> jb
>
> (reply address in rot13, unscramble first)[/color]

* Chinmoy Mukherjee:[color=blue]
> [top-posting]
> [extranous quoting][/color]

Please don't top-post in this group

Please don't quote irrelevant material.

Read the FAQ.


* Chinmoy Mukherjee:[color=blue]
> * Jakob Bieling:[color=green]
> > * Chinmoy Mukherjee:[color=darkred]
> > > when the node structure is like
> > >
> > > struct node {
> > > node *next;
> > > node *rand; (// random is supposed to point to another
> > > node
> > > int value;
> > > }[/color]
> >
> > Traverse list, create copy of each node, link nodes correctly
> > together.[/color]
>
> Thanks Jakob.
> But how to I remember the rand poniters of each node
> the idea is to retain the strcuture[/color]

Already answered in this thread, why don't you read the answers?

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

> Now question is how do I copy the link list to[color=blue]
> another link list so that the overall structure is retained.
> Regards,
> Chinmoy[/color]

Don't you read replies given to your question?
I and Steinbach gave you a way to do that.