Story of a funny linked list

 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.

	package org.avasthi.java.cli;
	import javafx.util.Pair;
	import java.util.HashMap;
	import java.util.Map;
	public class List {
	public Node add(int value) {
	if (head == null) {
	head = new Node(value, null, null);
	return head;
	}
	else {
	Node current = head.next;
	Node prev = head;
	while (current != null) {
	prev = current;
	current = current.next;
	}
	prev.next = new Node(value, null, null);
	return prev.next;
	}
	}
	public Node add(int value, Node pointsTo) {
	Node n = add(value);
	n.other = pointsTo;
	return n;
	}
	public List clone() {
	Map<Node, Pair<Node, Node> > otherToOriginalNode = new HashMap<>();
	Map<Node, Node > allNodes = new HashMap<>();
	Node current = head;
	List newList = new List();
	while(current != null) {
	Node newNode = newList.add(current.value);
	if (current.other != null) {
	otherToOriginalNode.put(current.other, new Pair<>(current, newNode));
	}
	allNodes.put(current, newNode);
	Pair<Node, Node> orphan = otherToOriginalNode.get(current);
	if (orphan != null) {
	orphan.getValue().other = newNode;
	}
	current = current.next;
	}
	for(Map.Entry<Node, Pair<Node, Node>> e : otherToOriginalNode.entrySet()) {
	e.getValue().getValue().other = allNodes.get(e.getKey());
	}
	return newList;
	}
	public void print() {
	if (head == null) {
	System.out.println("EMPTY");
	}
	else {
	Node current = head;
	while (current != null) {
	System.out.println(String.format("%d%s", current.value, (current.other == null ? "" : String.format(" Points to %d", current.other.value))));
	current = current.next;
	}
	}
	}
	private Node head;
	}

view raw List.java hosted with ❤ by GitHub

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.