Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, ensure you are not making multiple copies of the same node.
提示 2
You may want to use extra space to keep old_node ---> new_node mapping to prevent creating multiple copies of the same node.
提示 3
We can avoid using extra space for old_node ---> new_node mapping by tweaking the original linked list. Simply interweave the nodes of the old and copied list. For example:
Old List: A --> B --> C --> D
InterWeaved List: A --> A' --> B --> B' --> C --> C' --> D --> D'
提示 4
The interweaving is done using next pointers and we can make use of interweaved structure to get the correct reference nodes for random pointers.
