Recently I was presented with this problem, for a moment I was completely blanked on how to solve this problem. I had to think for some time and finally found a solution. Let's first look at the problem.
Let's assume we have a simple singly linked list. The only modification is that each node of the linked list also has another link, let's call it other. For some of the elements of the list, the link other contains a pointer to some other element in the list. Now, we have to write a clone function that makes a deep copy of the list.
The salient method is the clone method in the class. The challenge is that other pointer can come in any other. A node earlier in the list can point to a node later in the list and vice versa. So we have to basically run two passes on the list.
In the first pass, we make a regular copy of the list and create two hash-maps. The first hash-map contains other pointer as the key and the old and new node as the value pair. The second hash map contain a mapping of each node and its corresponding new map.
Once we complete the simple copy of the list, we traverse through the first map and find all corresponding new nodes for corresponding old nodes to which the other pointer is pointing to and then we retrofit the list.
So that's how I was able to solve the problem of funny linked list.
