题目：https://oj.leetcode.com/problems/copy-list-with-random-pointer/

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

1. Shallow copy

拷贝时仅仅复制的是指针或者引用， 也就是说 数据仅存在一份。当然，得到效率的同时，存在的问题就是，如果原来的数据改变了，复制后的对象也改变了，因为仅仅存在一份数据!!!

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

2. deep copy

拷贝时不仅复制指针或者引用，把指向的数据重新复制一份，如果原来的数据改变了，复制后的对象不会改变，因为它们拥有的是两份不同的数据。

3. Lazy copy

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

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

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

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

回到这道题目我们需要怎么做？

其实这道题在剑指offer上出现过，我也实现过，今天再次实现比以前实现做的更好一些。以前实现：http://blog.csdn.net/huruzun/article/details/22292451

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

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

Step 2: 将链表拆成两个链表 。

实现一定注意一点：分离两个链表，这里特别注意不能改动原先链表状态，否则无法AC。

public class Solution {	public RandomListNode copyRandomList(RandomListNode head) {		if (head == null) {			return null;		}		RandomListNode p = head;		RandomListNode next = null;		// 先完成copy		while(p!=null){			next = p.next;			RandomListNode node = new RandomListNode(p.label);			node.next = next;			p.next = node;			p = next;		}		p = head;		RandomListNode q = p.next;		// 复制random		while(p!=null){			if(p.random!=null){				q.random = p.random.next;			}			p = p.next.next;			// q移动两步指针则需要先进行判断			if(p!=null){				q = q.next.next;			}					}		RandomListNode newHead = head.next;		RandomListNode pHead = head;		RandomListNode qHead = newHead;		// 分离两个链表，这里特别注意不能改动原先链表状态。		while(pHead!=null ){			pHead.next = qHead.next;			if(qHead.next!=null){				qHead.next = qHead.next.next;			}			pHead = pHead.next;			if(pHead!=null){				qHead = qHead.next;			}		}		return newHead;	}}

Copy List with Random Pointer