Deep copy linked list with a random pointer

Question

I had this as an interview question through phone through an online text editor.

The input is a linked list and in addition to a next pointer there is a random pointer that can point to any node in the list. Create a deep copy of the linked list and return the head of the new copy.

This my code below, which does the above Can some one review the code provide some feed back. Also is 28 mins too much for this code for a phone interview? I took my time but still made a few mistakes which has been fixed here already.

public class Node {
 public int val;
 public Node next;
 public Node random;
 public Node(int val) {
 this.val = val;
 next = null;
 random = null;
 }
}
class CopyUtil {
 Node deepCopy(Node head) {
 if (head == null) return head;
 Dictionary < Node, Node > nodePool = new Dictionary < Node, Node > ();
 Node current = head;
 Node newHead = new Node(head.val);
 nodePool.Add(current, newHead);
 newHead.random = getNode(nodePool, head.random);
 Node returnHead = newHead;
 while (current.next != null) {
 newHead.next = getNode(nodePool, current.next);
 newHead.next.random = getNode(nodePool, current.next.random);
 current = current.next;
 newHead = newHead.next;
 }
 return returnHead;
 }
 Node getNode(Dictionary < Node, Node > nodePool, Node current) {
 Node ret = null;
 if (current==null) return ret;
 if (nodePool.ContainsKey(current))
 ret = nodePool[current];
 else {
 ret = new Node(current.val);
 nodePool.Add(current, ret);
 }
 return ret;
 }
}

Mistakes:

• 1) Had a return type for constructor.
• 2) Had private (unspecified protection levels) Node values.
• 3) I was working with newHead.random instead of newHead.next.random inside loop.
• 4) Missed new keyword in one of initialization of Dictionary.
• 5) Missed null check when I moved to code to a util function.

Tips:

• 1) The editor was in plain text and 1/2/4 were stupid and silly mistakes which should have been caught if I patiently reviewed the code.
• 2) Practice on a plain notepad editor.
• 3) Have a headphone. Its important to collect your thoughts without worrying about dropping your phone.
• 4) Silly mistakes creeped in when I moved some code lines into a function and was doing some copy/paste. Be careful when you refactor your code during interviews.
• 5) Think your are submitting your code to codereview in stackexchange. lol.

Answer 1

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

1. To use properties rather than fields;
2. To make the setters private, and move the clone method into Node;
3. Since the specification doesn't say anything about the contents, to parameterise as Node<T> 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 < Node, Node > nodePool = new Dictionary < Node, Node > ();
 Node current = head;
 Node newHead = new Node(head.val);
 nodePool.Add(current, newHead);

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

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 < Node, Node > 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<Node, Node>.

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;