Create Copy List with Random Pointer

[jawakarsri]

Time Complexity:

•   O(n) due to three passes over the list:
1.  One pass to create the interwoven list.
2.  One pass to assign the random pointers.
3.  One pass to separate the original and copied nodes.

Space Complexity:

•   O(1) since no additional space other than a few pointers is used.

[jawakarsri]

Key Steps:

1.  Node Creation:
•   It iterates over the original list and creates new nodes (deep copy of each node).
•   It checks the HashMap to determine whether a new node needs to be created or reused from the map.
2.  Mapping Random Pointers:
•   For each node, the random pointer is set using the stored mapping. If the random node isn’t already in the map, it creates a copy and adds it to the map.
3.  Final List:
•   After the loop finishes, the deep copy list is fully constructed and returned.