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

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

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.