https://leetcode.com/problems/copy-list-with-random-pointer/description/
<aside> ❗
Do not look at the writeup before trying it out yourself.
</aside>
We have to create a deep copy of the given linked list. Apart from data and *next , every node contains *random which can point to, well, any random node. It is a fairly simple problem, we can create a new list first and store the new and old pointers for each node in a map and then in the next pass we can link the random pointers.
How do we do it without using extra space and other DS? Interesting. We can create new nodes and insert them just after the corresponding old node. So, n1 -> n2 -> ... becomes n1 -> N1 -> n2 -> N2 -> ... where n is the old node and N is the new copy. Now suppose, n1 ’s random links to n8 , then N1 ’s random must link to N8 which comes directly after, you guessed it, n8 , so we can directly say n1 -> next -> random = n1 -> random -> next (and of course also make sure that the random is not null). Makes sense?
// Implementation will only be shared once everyone has tried.