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.

/**
 * 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) {}
 * };
 */
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 == NULL) return head;
		//将oldList的每一个节点之后，插入一个newNode.
		RandomListNode *oldListNode = head;
		while(oldListNode != NULL)
		{
			RandomListNode *newListNode = new RandomListNode(oldListNode->label);
			newListNode->next = oldListNode->next;
			newListNode->random = oldListNode->random;
			oldListNode->next = newListNode;
			oldListNode = oldListNode->next->next;
		}
		//update newListNode上的random结点关联的结点
		oldListNode = head;
		while(oldListNode != NULL)
		{
			if(oldListNode->random != NULL)
			{
				oldListNode->next->random = oldListNode->random->next;
			}
			oldListNode = oldListNode->next->next;
		}
		//分离oldListNode与newListNode
		RandomListNode *newListNode = new RandomListNode(0);
		newListNode->next = head;
		oldListNode = head;
		RandomListNode *resultListNode = newListNode;
		while(oldListNode != NULL)
		{
			newListNode->next = oldListNode->next;
			oldListNode->next = newListNode->next->next;
			newListNode = newListNode->next;
			oldListNode = oldListNode->next;
		}
		return resultListNode->next;
    }
};

leetcode - Copy List with Random Pointer