CareerCup

I am not quite understand the answer above but based on the same idea of using just a O(1) space the solution could be following:
1)[Merge listst]Create list B this way: for each NodeA in A create a NodeB in B , copy NEXT ptr to NodeB: NodeB{NEXT} = NodeA{NEXT} and change NEXT ptr in NodeA to this newly created node in B: NodeA{NEXT}=NodeB;
2) go through the list A (NB: you have to jump through the nodes of B!) and set NEXTRND ptr in next B nodes to the next ptrs after next_random nodes: NodeA{NEXT}{NEXTRND}=NodeA{NEXTRNF}{NEXT};
After that all NEXTRND nodes in list B will be pointing to correct nodes in B;
3) [Un-merge]. For each node in A and in NEXT node B set correct NEXT ptrs:
node=headA;
while(node){tmp = node{NEXT}; node{NEXT}=tmp?tmp{NEXT}:NULL; node=tmp;}
After this process all {NEXT} nodes in both lists A and B will be correct

It seems that nobody replies. Just throw my idea on the table.

Assume the node has two pointers, one is called next, the other is called randomnext.

Go through the list by using "next", create a hashmap A with (Node -> serial number(1,2,3,...)). Go through the list again to create another hashmap(list) B with (serial number -> the randomnext's serial number) by the aid of A.

duplicate the list by using "next" and create the hasmap C with (serial number -> Node). Go through the newly created list again, use the current position (serial number) to check the hashmap(list) B to find out the position of the randomnext's serial number. Use the hashmap C to find out the node. Link the randomnext node.

I think only one hash map is enough. During first traversal on list, create a haspmap with oldpointer to new pointer. Now traverse the original list again and and link the newrandom pointer.

Here is the approach with single traversal and single hashtable:

class Node
    {
        public int data;
        public Node Next = null;
        public Node RandomNext = null;
        private Node() { }
        public Node(int d)
        {
            data = d;
        }
    }

public static Node CopyList(Node head)
        {
            Node newHead = null;
            Hashtable ht = new Hashtable();
            Node newNode;
            Node currentNode = null;
            while (head != null)
            {
                int hcode=head.GetHashCode();
             if(!ht.ContainsKey(hcode)   )
             {
                 newNode=new Node(head.data);
                 ht.Add(hcode, newNode);
             }
             else
             {
                 newNode=(Node)ht[hcode];
             }
             if (newHead == null)
             {
                 newHead = newNode;
                 currentNode = newNode;
             }
             else
             {
                 currentNode.Next = newNode;
                 currentNode = currentNode.Next;
             }
             if (head.RandomNext != null)
             {
                 hcode=head.RandomNext.GetHashCode();
                 if (!ht.ContainsKey(hcode))
                 {
                     newNode = new Node(head.RandomNext.data);
                     ht.Add(hcode, newNode);
                 }
                 else
                 {
                     newNode = (Node)ht[hcode];
                 }
                 currentNode.RandomNext = newNode;
             }
             head = head.Next;
            }
            return newHead;
        }

B: add a couple of lines explaining the flow of your algo/logic. :-)

Anonymous on October 08, 2009: B'coz we're not as retarded as you are. Your moron !
If your understand why d0nt you explain, you scruffy crappy idiot.

are you sure we know which pointer points to next node and which points to random node? What if they're just two pointers and you cant tell who is pointing the next node and the random node.

There is no need to create hashmap. let the two lists be A and B.

while copying a node nb in B from node na in A, change the random pointer of na to na->rand^nb. Also copy the original data and random pointer of na in node nb.

After copying all the nodes, again traverse two lists and this time,
nb->rand = nb->rand^na->rand = node in list b to which nb should point.

A third pass will be needed to restore the original random pointers in A.
na->rand = na->rand^nb^nb = na->rand;

typo: NodeA{NEXTRNF}{NEXT}; -> NodeA{NEXTRND}{NEXT};
NB: NodeA{NEXT} - is a node in B list!

though looks complex initially its simple one....

A: Original List
B: Copy List

First pass:
make a copy of linked list using next ptr of A. With this..
B will have every next ptr perfectly placed.
While copying each node, make nodeA->next = nodeB; and NodeB->random=nodeA;

Second Pass:
Traverse B and make nodeB->random = nodeB->random->random->next;

Done; Correct me if something is wrong.

you will need some kind of hash map to remember where ->random points. Also ->random in list A and B are different.

This is an O(n) solution , but yeah it takes 2 hash map.

First, traverse through list A , while traversing store in hash map_A the <address_old_list_node, index> and copy this node to the new linked list.

when creating new linked list , store the index and the address_new in another hash map_B <index, address_new_malloced_node>.

So at the end of the pass one, we have two hash maps and two list. New list does not have the random pointers.

In second pass, traverse through the first list for every random pointer address get the index of the pointer from map_A and get the corresponding new address for that index from map_B and point the random pointer of the list B to this address.

So totally in two pass we have the linked list.

Why not this:

Random&Next(CurrentA, CurrentB)
{
CurrentB.next = CurrentA.next;
CurrentB.value = CurrentA.value;
CurrentB.random = CurrentA.random;
Random&Next(CurrentA.Random, CurrentB.Random);
Random&Next(CurrentA.next, CurrentB.next);
}

1. Go over the original list following next links and create the new list. (new list will contain only the next pointers for now) Meanwhile put the new nodes in a hash map. (the key is the address of the old node and the value is the address of new node)
2. In the second scan, go over both lists in parallel. For each arbitrary pointer in the original list, fetch the address of corresponding node from hashmap.

it's a graph so, you can copy it DFS style marking the nodes with a 'visited' marker. Complexity O(|V|+|E|)

Can you elaborate more on your graph method?

Following method should work with O(n) complexity and no extra space.

Original List a1->b1->c1->d1->e1

Let Random pointers of original list be a1->c1, b1->d1, c1->a1, d1->c1, e1->e1

Start traversing the original list, while traversing create new nodes as well.
When u do that, do one more thing, point the random pointer of the original node to the newly created node, and
point the random pointer of this newly created node to the node which was pointed by random pointer of the original node.

After performing the above action

Original List a1->b1->c1->d1->e1

Random pointers of original list
a1->a2, b1->b2, c1->c2, d1->d2, e1->e1

New list a2->b2->c2->d2->e2

Random pointers of new list:
a2->c1, b2->d1, c2->a1, d2->c1, e2->e1

Now traverse both the lists again simultaneously

since a1->a2, a2->c1 and c1->c2 (perform actions on random pointers)=> a1->c1, a2->c2
b1->b2, b2->d1 and d1->d2 (perform actions on random pointers)=> b1->d1, b2->d2
c1->c2, c2->a1 and a1->a1 (perform actions on random pointers)=> c1->a1, c2->a2

thus new similar list is formed

could anyone explain the question? how does it mean?

tech-queries.blogspot.com/ 2011/04/copy-linked-list-with-next-and-random.html

create the copy of 1 and insert between 1 & 2, create the copy of 2 and insert between 2 & 3.. continue in this fashion add the copy of N to Nth node

Now copy the arbitrary link in this fashion Original->next->arbitrary = Original->arbitrary->next; TRAVERSE TWO NODES;

This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.

now restore the Original and copy linked lists in this fashion in a single loop.
Original->next = Original->next->next;
copy->next = copy->next->next;

Make sure that last element of original->next is NULL.

struct node *clone(struct node *head)
{
HasMap h=new HashMap();

for(current1=head;current1;current=current->next)
{
temp=malloc(sizeof(struct node));
h.put(current,temp);

struct node *clone(struct node *head)
{
HasMap h=new HashMap();
struct node *current1,current2,*prev=NULL,*head2;
for(current1=head;current1;current1=current1->next)
{
temp=malloc(sizeof(struct node));
temp->data=current->data;
if(prev==NULL)
{
head2=temp;
}
else
{
prev->next=temp;
}
h.put(current1,temp);
prev=temp;
h.put(current,temp);
}
for(current1=head,current2=head2;current1;current1=current1->next)
{
current.ptr=h.get(current.ptr);
}
return head2;
}

// arbitrary pointer linked list :)
// code have the complexity equals O(n)
struct node *createCopy(struct node *L)
{
struct node *temp,*temp1,*head;
if(L==NULL)
return NULL;
temp=L;
while(temp!=NULL)
{
if(!head)
{
head=(struct node*)malloc(sizeof(struct node));
temp1=head;
temp1->next=temp->next;
temp->next=temp1;
temp=temp1->next;
}
temp1=(struct node*)malloc(sizeof(struct node));
temp1->next=temp->next;
temp->next=temp1;
temp=temp1->next;
}

for(temp=L;temp!=NULL;temp=temp->next->next)
{
temp->next->arbit=temp;
}
temp=L;
while(temp!=NULL)
{
temp->next->arbit=temp->arbit->next;
temp1=temp->next;
temp->next=temp->next->next;
temp->next=temp->next->next;
temp=temp->next;
}

return head;



}

1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node
2) Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE
TWO NODES*/

This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
3) Now restore the original and copy linked lists in this fashion in a single loop.

original->next = original->next->next;
copy->next = copy->next->next;

4) Make sure that last element of original->next is NULL.

Time Complexity: O(n)
Auxiliary Space: O(1)