## Given linked list each nodes contains :

**1.** Node data

**2.** Pointer to next node.

**3.** Pointer (arbitrary pointer) to any node in the list (Not just previous).

We need to write a program which will create a copy of the list.

### Example

**Time complexity : (n)**

**Space Complexity : O(n)**

## Algorithm

In this algorithm we use hashing,

**a.** Traverse the input linked list and make a copy of it in terms of data(into a array or vector).

**b.** Create a hash map with pair of key, (input list node, copied linked list node)

**c. ** Traverse the input list once again and use the hash map to set the next and random pointer of cloned linked list.