Home » Technical 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)


Reading Time - 1 mins

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.

READ  Merge Two Sorted Lists Leetcode
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions