题目：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.

分析：

题目给出了一个特殊的单链表。链表的每一个节点多了个指针域: random. 随机只向链表的某一个 node。

题目要求我们给出这个链表的一个 deep copy.

首先，何为 deep copy ??

Part 1:  三种 Object Copy 的对比(以 Array 为例)

1. Shallow copy

拷贝时仅仅复制的是 指针 或者 引用， 也就是说 数据仅存在一份。

当然，得到效率的同时，存在的问题就是，如果原来的数据改变了， 复制后的对象也改变了，因为仅仅存在一份数据!!!

Note: 其实是出于效率的考虑，在某些场合，并不需要多份数据时，可以采用 shallow copy

2. Deep copy

与 shallow copy 不同，deep copy 复制后，数据有多份。因此， deep copy 也比较费时。

在 C++ 中，可以自行定义类的 copy 构造函数来实现 deep copy.

Python 中，array 默认的复制是 shallow copy,  可以采用 copy 模块的 deep copy

3. Lazy copy

这是一种上述两种策略的组合。又称为 copy-on-write.

最初复制时，采用效率更高的 shallow copy,  同时用一个计数器 counter 记录当前share数据的对象数目。

当需要对数据进行修改时，根据 counter, 采用 deep-copy，

也就是当需要 deep-copy  时，才调用比较费时的 deep-copy.

回归本题：deep copy of the list

对于正常的单链表， 一份 deep copy 非常的容易。只要对链表循环一次，依次复制节点即可。

但是问题的困难在于： Node 多了一个 random 指针域。

对于 random 域：

        如果 原链表： Node i 指向 Node j

                 新链表： Node i 同样指向 Node j（新链表的node）

如何能够找到新链表每个节点 random 域 所指向的节点呢？？

思路： Step 1: 首先指向在原链表的每个节点后面，复制一个新的节点，原链表长度变为 2 倍

                          random 指针指向的是 原链表节点 random 指针指向的节点的后面的那个节点

              Step 2: 将链表拆成两个 lists

/**
 * 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) {
        RandomListNode *tHead = head;
        RandomListNode *next = NULL;
        while(tHead)
        {
            next = tHead->next;
            RandomListNode *node = new RandomListNode(tHead->label);
            node->next = tHead->next;
            //node->random = tHead->random;
            tHead->next = node;
            tHead= next;
        }
        tHead = head;
        while(tHead)
        {
            if(tHead->random) tHead->next->random = tHead->random->next;
            tHead = tHead->next->next;
        }
        RandomListNode *retHead = NULL;
        RandomListNode *tRet = NULL;
        
        tHead = head;
        RandomListNode *next2 = NULL;
        while(tHead)
        {
            if(retHead == NULL)
            {  
                next2 = tHead->next->next;
                retHead = tHead->next;
                tRet = retHead;
                tHead->next = next2;
                tHead = next2;
            }
            else
            {
                next2 = tHead->next->next;
                tRet->next = tHead->next;
                tHead->next = next2;
                tHead = next2;
                tRet = tRet->next;
            }

        }
        return retHead;
    }
};

LeetCode----Copy List with Random Pointer 深度拷贝，浅度拷贝，Lazy拷贝解析