Cloning link list with Random node pointer

You are given a link list which contains the data, next pointer and random pointer which points any random node in the list. Your task is to clone this list.

This problem can be solved using multiple approaches.

Approach 1: Brute force approach

• Clone the new list.
• Now traverse form start each time in both list for finding  out the random nodes and update the random node.

This approach will take the O(n^2) time complexity.

 

Approach 2: Use Temporary Storage 

Simply go on creating the clone and storing the map of old pointer address to its respective new pointer address and during cloning copy the random pointer address as is in the new list.Let's say pHead is pointer to old list head and pNewHead is pointer to new list, then the map will contain key as pHead and value will be pNewHead. Also pNewHead->pRandom = pHead->pRandom.

Now once new list is ready, traverse it from head again and replace each random pointer with its respective new random pointer by look up in the map.  

This way with the temporary storage of map we can clone the list as shown in below code.

struct RandomNode {     int data;     RandomNode * pNext;     RandomNode * pRandom;     RandomNode(int value) : data(value), pNext( NULL), pRandom( NULL)     {        } }; typedef  map<RandomNode *, RandomNode *> RandNodeMap; RandomNode *  CloneListUsingMap(RandomNode * pHead) {     if (pHead)     {         RandNodeMap nodeMap;         RandomNode * pTemp = pHead;         RandomNode * pNewHead = new RandomNode(pTemp->data);         pNewHead->pRandom = pTemp->pRandom;                RandomNode * pNewTemp = pNewHead;         nodeMap.insert(make_pair(pTemp, pNewTemp));                pTemp = pTemp->pNext;         while (pTemp)         {             RandomNode * pClone = new RandomNode(pTemp->data);             pClone->pRandom = pTemp->pRandom;             nodeMap.insert(make_pair(pTemp, pClone));             pNewTemp->pNext = pClone;                    pNewTemp = pNewTemp->pNext;             pTemp = pTemp->pNext;         }         pNewTemp = pNewHead;         while (pNewTemp)         {             RandNodeMap::const_iterator kit =  nodeMap.find(pNewTemp->pRandom);             pNewTemp->pRandom = kit->second;             pNewTemp = pNewTemp->pNext;         }         return pNewHead;     }     return NULL; }

The issue with the above solution is that we require the temporary storage for storing the addresses in the map.

Approach 3: Modify the existing list temporary

If we want to avoid the temporary storage, we can do that just by modifying the existing list. 
We will create the new list in the same fashion as created above. Means copy the random node address as is in the clone node random address location.
Also during creating the cloned list, attache every cloned node will be the next node of existing node.  Now for updating the random node we have to visit just the next node of the random node.
Once random nodes are updated separate the two lists.
  

RandomNode * CloneList(RandomNode * pHead) {     if (pHead)     {         RandomNode * pNewHead = new RandomNode(pHead->data);         RandomNode * pNew = pNewHead;         pNewHead->pRandom = pHead->pRandom;         RandomNode * orgList = pHead->pNext;         pHead->pNext = pNewHead;         pNewHead->pNext = orgList;         while (orgList)         {             //Create new node             RandomNode * nextNode = new RandomNode(orgList->data);             nextNode->pRandom = orgList->pRandom;                //Current list next will be new node next             nextNode->pNext = orgList->pNext;             RandomNode * tempNode = orgList;             orgList = orgList->pNext;                        //Insert it to existing list             tempNode->pNext = nextNode;         }                //Now update the random nodes of new list         pNew = pNewHead;         while (pNew)         {             pNew->pRandom = pNew->pRandom->pNext;             pNew = pNew->pNext;             if (pNew)                 pNew = pNew->pNext;             else                 break;         }         //Break entire list in to original list and cloned list         orgList = pHead;         pNew = pNewHead;         while (pNew)         {             orgList->pNext = pNew->pNext;             orgList = orgList->pNext;             if (orgList)                 pNew->pNext = orgList->pNext;             else             {                 pNew->pNext = NULL;                 break;             }             pNew = pNew->pNext;         }         return pNewHead;     }     return NULL; }

This technique just requires total three iterations of the list.