title: How to create deep copy of Linked List that maintain same order
body: <p>I got asked the following question at a job interview that I could not figure out. You are given a Linked List of the following Node elements:</p>
  
  <pre><code>class Node {
    int value;
    Node next; // points to next element in list
    Node random; // points to one random element of list
  }
  </code></pre>
  
  <p>Say you have a Linked List of these nodes (say 20 nodes) where "next" points to the next element and "random" points to one other element of the list (meaning, can point to one specific but randomly chosen element in the list).  I.e., 1st element's "random" can point to node #5, Node 2nd element's random can point to node #9, etc.</p>
  
  <p><strong>Question:</strong> How do you create a brand new Linked List that is a deep copy of this list of Nodes but maintains the same order and same linkages for both "random" and "next"? </p>
  
  <p>In other words, if one traverses this new list using any of these 2 pointers the order of traversal would be the same.</p>
  
  <p>The other topic some people referenced would clone the same pointers via default clone and that would not address this challenge.</p>