Deep copy linked list with a random pointer
public class Node {
 public int val;
 public Node next;

 public Node random;

 public Node(int val) {
  this.val = val;
  next = null;
  random = null;
 }
}



I understand that this was for a demo rather than production code, but it's really neither idiomatic C# nor good OO. I would have preferred


To use properties rather than fields;
To make the setters private, and move the clone method into Node;
Since the specification doesn't say anything about the contents, to parameterise as Node&lt;T&gt; rather than forcing the contents to be int (although maybe you clarified this with the interviewer and forgot to include it in the question).


I'm also not keen on exposing the Node class directly, although I'm not sure what API the enclosing LinkedList class would have with respect to the random links.




class CopyUtil {

 Node deepCopy(Node head) {



Node is public: why is CopyUtil internal and deepCopy private?

Why is neither the class nor the method static?




  if (head == null) return head;
  Dictionary &lt; Node, Node &gt; nodePool = new Dictionary &lt; Node, Node &gt; ();
  Node current = head;
  Node newHead = new Node(head.val);

  nodePool.Add(current, newHead);



Stylistically, I think there's far too much whitespace in Dictionary&lt;Node, Node&gt;. I suspect that you're applying C++ style guides designed to avoid parsing ambiguity with &gt;&gt; vs &gt; &gt;.

Why not Node newHead = getNode(nodePool, head)?

There is plenty of room for debate around when to use var, but I think few people nowadays would favour writing out an explicit type twice when calling a constructor.




  newHead.random = getNode(nodePool, head.random);



I think that with a bit of thought you could remove the special case head == null and this line and treat them as part of the general case in the loop.




  Node returnHead = newHead;



This is the first warning sign that newHead is a bad name. It's the head when first assigned, but later on it's really newCurrent.




 Node getNode(Dictionary &lt; Node, Node &gt; nodePool, Node current) {



I could have mentioned this above when the dictionary was created, but this is a better place: code to the interface, not the implementation. nodePool should be an IDictionary&lt;Node, Node&gt;.

Why current? That makes sense in deepCopy, but here a better name would be oldNode.




  Node ret = null;
  if (current==null) return ret;



I don't understand the point of ret given that you're not following the single exit principle.




  if (nodePool.ContainsKey(current))
   ret = nodePool[current];



This searches through the dictionary's data structures twice. The .Net API has a nicer way of doing it:

Node newNode;
if (nodePool.TryGetValue(current, out newNode)) return newNode;