Home » Interview Questions » LinkedList Interview Questions » Clone a linked list with next and random pointer (Hashing)

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.

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

READ  Merge K Sorted Linked Lists
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions