CareerCup

The method I came across uses <map> container of C++ STL. A map is actually an associative array which has a key and a value associated with that key.

Steps: (The code syntax isn't coming properly in comments so check online)

1. Copy the original list to new list with next pointers intact, leave arbit pointers for now

2. While copying make a map

map <node*, node*> map_hash

In our case map will have the key as the original list node and value as copy list node

3 Map would be somewhat like this

Original --> Copy
Node1 --> Node1(copy)
Node2 --> Node2(copy)
Node3 --> Node3(copy)

4 Start from head of copy list, corresponding to this copy list node we have the original list node in map. We can access it using an iterator.

map<node*, node*>::iterator i
 i = map_hash.begin()
 copy_node->arbit = map_hash.at((*i).first->arbit)

Note:- (*i).first = original_List node
(*i).first->arbit = arbitrary node pointed by (*i).first
map_hash.at() gives the value stored at that key

What we are doing is for each copy_List node we take its corresponding original_List node then find its arbit node, next we use our map to find the node in our copy_List corresponding to this arbit node and assign it to the arbit pointer of the copy_List node

Hope this will help!!!

This problem was already discussed many times. I've chosen the most elegant idea and implemented it

If we want to copy such linked list we should do following steps:

1) Create copy for each node and insert it next to node.
Example: was A->B->C became A->A'->B->B'->C->C'

2) Copy random links
Example: if there were connection A->C let's make connection A'->C'

3) Remove link between original node and it's copy (separate copy and original)

Totally we need to traverse three times through linked list (O(3N)) and O(1) extra memory
Here is C# implementation.

//O(3N) operations
        public static Node Copy(Node start)
        {
            Node copy,result, original = start;
            //First traverse
            //For each node insert copy of node next to it
            while (original != null)
            {
                copy = new Node
                {
                    Val = original.Val,
                    Next = original.Next
                };
                original.Next = copy;
                original = copy.Next;
            }

            //Second traverse
            original = start;
            //copy random links
            //Example was A->C , copy link to nodes' copies A'->C' (-> means "Random")
            while (original != null)
            {
                copy = original.Next;
                if (original.Random != null)
                    copy.Random = original.Random.Next;
                else
                {
                    //this "else" block can be safely removed , because by default Random is null
                    //I save this code only for your understanding
                    copy.Random = null;
                }
                original = copy.Next;
            }

            //Third traverse
            original = start;

            //save the result , because now the code will destroy links between
            //original nodes and copies
            result = start.Next;

            //destroy links between original nodes and copies
            while (original!=null)
            {
                copy = original.Next;
                original.Next = copy.Next;
                if (original.Next != null)
                    copy.Next = original.Next.Next;
                original = original.Next;
            }
            return result;
        }

DUHHH. USE A HASH TABLE DUHHH.

Create cloned nodes and hash (key=cloned from, valu=clone itself)

Use that somehow, okay?