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.

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.

Translate »