import java.util.*; public class LinkedListClone { private static class Node { int value; Node next; Node random; @Override public String toString() { return (value + " " + ((next != null)?next.value:"-") + " " + ((random != null)?random.value:"-")); } } public static Node clone(Node head) { Map mapper = new HashMap(); return helper(head, mapper); } private static Node helper(Node node, Map mapper) { if(node == null) { return null; } if(mapper.containsKey(node)) { return mapper.get(node); } Node newNode = new Node(); newNode.value = node.value; if(mapper.containsKey(node.next)) { newNode.next = mapper.get(node.next); } else { newNode.next = helper(node.next, mapper); } if(mapper.containsKey(node.random)) { newNode.random = mapper.get(node.random); } else { newNode.random = helper(node.random, mapper); } return newNode; } public static void main(String[] args) { Node n = new Node(); n.value = 1; Node n1 = new Node(); n1.value = 2; Node n2 = new Node(); n2.value = 3; n.next = n1; n1.next = n2; n.random = n2; Node newNode = LinkedListClone.clone(n); System.out.println(newNode); System.out.println(newNode.next); System.out.println(newNode.random); } }