```
public RandomListNode copyRandomList(RandomListNode head)
{
// ex. 1.random->3
// 1.next->2
// 2.random->1
// 2.next=3
if (head == null)
{
return null;
}
RandomListNode iter = head;
// pass#1.
//In this iteration we will insert intermediate nodes or more like a prime.
//So 1->2->3 becomes 1->1'->2->2'->3->3'. Don't worry about random yet.
while (iter != null)
{
RandomListNode next = iter.next;
iter.next = new RandomListNode(iter.label);
iter.next.next = next;
iter = next;
}
// pass#2.
iter = head;
//Take care of the random pointer. The random of 1 should be pointed out to 1' and so on. Ex. if 1 had a random pointer to 2, we will do a random pointer from 1' to 2' in this step.
while (iter != null && iter.next != null)
{
RandomListNode random = iter.random;
if (random != null)
{
iter.next.random = random.next;
}
iter = iter.next.next;
}
// pass#3.
iter = head;
RandomListNode newListHead = iter.next;
// 1->1'->2->2'->3->3'
//Restore the list by making sure that every alternate pointer points to the the right one.
while (iter != null && iter.next != null)
{
RandomListNode temp = iter.next;
iter.next = temp.next;
iter = temp;
}
return newListHead;
}
```