Clone a linked list with next and random pointer (Hashing)  

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.

Please click Like if you loved this article?

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.

See also
Swap Nodes In Pairs
Please click Like if you loved this article?