↳

My take was the list had multiple pointers so more like a graph. One pointer to the next element and perhaps another to some non ordinal node. I can see doing one pass where you create the linked list node by node and keep the random pointer null. As you create your copy nodes, you hash the old object to point to the new one. Then you traverse the old list again, you can then do a get on the hash to populate the random pointer destination. I'm using hashCode() here but you could decorate your own Id. import java.util.HashMap; import java.util.Map; class Node { int value; Node next; Node random; public Node(int value) { this.value = value; } public Node(int value, Node next, Node random) { this.value = value; this.next = next; this.random = random; } public String toString() { return "Val: " + this.value + " next: " + ((this.next == null) ? "null" : this.next.value) + " random: " + ((this.random == null) ? "null" : this.random.value); } } public class CopyList { public static Node copyList(Node list) { if (list==null) { return null; } Node previous = null; Node head = null; Map oldToNew = new HashMap(); Node oldNode = list; while (oldNode != null) { Node current = new Node(oldNode.value); oldToNew.put(oldNode.hashCode(), current); if (previous == null) { head = current; } else { previous.next = current; } previous = current; oldNode = oldNode.next; } oldNode = list; // reset to head // Reset Random Pointers while (oldNode != null) { Node random = oldNode.random; if (random != null) { Node newNode = oldToNew.get(oldNode.hashCode()); newNode.random = oldToNew.get(random.hashCode()); } oldNode = oldNode.next; } return head; } /** * @param args */ public static void main(String[] args) { Node six = new Node(6, null, null); Node five = new Node(5, six, null); Node four = new Node(4, five, null); Node three = new Node(3, four, six); Node two = new Node(2, three, five); Node one = new Node(1, two, six); six.random = five; four.random = one; Node newHead = copyList(one); System.out.println("Old List: "); while(one != null) { System.out.println(one); one = one.next; } System.out.println(); System.out.println("New List: "); while(newHead != null) { System.out.println(newHead); newHead = newHead.next; } } } Less