给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。复制链表中的指针都不应指向原链表中的节点。

返回复制链表的头节点。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

解题思路

三步走策略

1. 第一步：在每一个节点后面添加一个 copy 节点
   A -> B -> C 变为 A -> A' -> B -> B' -> C - C'

2. 第二步：对原链表的random指向，在 copy 节点也同样指向

if (curr.random != null){
	curr.next.random = curr.random.next;
}

3. 第三步：将原链表和复制链表拆开

Java 实现

public Node copyRandomList(Node head) {
	if (head == null) return null;

	// 第一步 复制节点
	Node curr = head;
	while(curr != null){
		Node nextTemp = curr.next;
		Node currCopy = new Node(curr.val);
		curr.next = currCopy;
		currCopy.next = nextTemp;
		curr = nextTemp;
	}

	// 第二步 复制random指向
	curr = head;
	while(curr != null){
		if (curr.random != null){
			curr.next.random = curr.random.next;
		}
		curr = curr.next.next;
	}

	// 第三步 拆开
	curr = head;
	Node headCopy = head.next;
	while(curr != null){
		Node currCopy = curr.next;
		Node realNextTemp = curr.next.next;
		curr.next = realNextTemp;
		if (realNextTemp != null){
			currCopy.next = realNextTemp.next;
		}
		curr = realNextTemp;
	}
	
	return headCopy;
}