Clone a Linked List with the next and random pointer

We can clone a linked list with random numbers by maintaining a hash table. The hash table stores the mapping from a linked list node to its clone.

Algorithm: –

• Firstly, we will create the copy of node1 and then add or insert it between node1 and node2 in the ori Linked List. After that, we will create a copy of node2 and add it between node2 and node3 in ori and so on, add the copy of N after the nth node.
• Next, we will copy the given arb(arbitrary) link in the below fashion.

ori->next->arb = ori->arb->next;

• Now, we restore the ori linked list and copy linked list in the below fashion in a single loop.

ori->next = ori->next->next;

copy->next = copy->next->next;

• Then we are required to confirm the ori->next is null. If it null, return the cloned list.

Clone a Linked List with the next and random pointer - Tutorial And Example