[LeetCode] Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list

Analysis: A simple solution is to have a hashmap to store the relationship between the original and new node. Alternatively, you can create the new nodes in the original list, making the new and old nodes side by side. It will be looks like:

O1->N1->O2->N2...

To assign the random pointers, you can just do this: O1->next->random = O1->random->next

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) 
    {
        if(!head) return NULL;
        RandomListNode *p = head;
        while(p)
        {
            RandomListNode *next = p->next;
            RandomListNode *newNode = new RandomListNode(p->label);
            p->next = newNode;
            newNode->next = next;
            p = next;
        }
        p = head;
        while(p)
        {
            if(p->random)
            {
                p->next->random = p->random->next;
            }
            p = p->next->next;
        }
        RandomListNode dummy(0);
        RandomListNode *ret = &dummy;
        p = head;
        while(p)
        {
            RandomListNode *next = p->next->next;
            ret->next = p->next;
            ret = p->next;
            p->next = next;
            p = next;
        }
        return dummy.next;
    }
};