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.
- 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.