# Question

Formatted question description: https://leetcode.ca/all/138.html

138	Copy List with Random Pointer

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.

The Linked List is represented in the input/output as a list of n nodes.
Each node is represented as a pair of [val, random_index] where:
* val: an integer representing Node.val
* random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Constraints:
-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.



# Algorithm

Three steps, with no extra space:

1. Copy a new node behind each node in the original linked list.

2. Assign values ​​to the random pointers of new nodes in turn, and this assignment is very easy cur->next->random = cur->random->next.

3. Disconnect the linked list to get a new linked list after deep copy.

For example, for example, the original linked list is 1(2) -> 2(3) -> 3(1), and the node pointed to by its random pointer is in parentheses, so this solution is to first traverse the original linked list. Copy a same node after each node, but the random pointer of the copied node is still empty, then the original linked list becomes 1(2) -> 1(null) -> 2(3) -> 2(null ) -> 3(1) -> 3(null). Then the second traversal is to assign the correct value to the random pointer of the copy node, and the original linked list becomes 1(2) -> 1(2) -> 2(3) -> 2(3) -> 3 (1) -> 3(1), note that the assignment statement is:

cur->next->random = cur->random->next;

Here cur is the node in the original linked list, cur->next is the node of the copied linked list, and cur->next->random is the random pointer of the copied linked list. cur->random is the node pointed to by the random pointer of the original linked list node. Because it points to the node of the original linked list, we have to add another next to point to the node of the copied linked list. The last traversal is to disconnect the original linked list from the copy linked list.

Java