Problem overview
Each ListNode has a val, a next pointer and a random pointer. The random pointer can lead to any node in the list, including the node itself, or to null. CopyRandomList(head) must build a deep copy: exactly n brand new nodes with the same values, where the copies' next and random pointers point to other copies, never to original nodes. It returns the head of the copy, or null for an empty list.
In the first example, the input [[7,null],[13,0],[11,4],[10,2],[1,0]] lists each node as [val, random_index]. Node 13 has its random pointer on node 0 (the 7), node 11 points to node 4 (the 1), and so on. The copy must have the same shape: its second node's random pointer leads to the copy of the first node, not to the original 7. The note asks for O(n) time and at most O(n) extra space.
Approach: map every original node to its copy
The difficulty is that a random pointer can lead forward, backward, or to the node itself. When you copy a node, the node it points to may not have a copy yet. Building the list in one pass runs into this constantly.
The fix is to split the work in two:
- Pass one creates a copy of every node, with just the value, and records it in a dictionary keyed by the original node.
- Pass two wires up the pointers. By now every original has a copy in the dictionary, so for any node the copies of its
nextandrandomtargets are one lookup away.
The dictionary costs O(n) extra space, which the problem allows. The lesson on the same problem that follows this one gets rid of the dictionary by weaving the copies into the original list. This lesson takes the clearer route first.
Step by step
- Create the map.
copiesis aDictionary<ListNode, ListNode>: original node in, copy out.ListNodedoesn't overrideEqualsorGetHashCode, so the dictionary compares keys by reference. Two nodes with the same value are still two different keys. - Start a cursor.
nodebegins athead, soheaditself stays put. The second pass and the return both need it. - Loop while
node != nullto visit every original node. - Store a value-only copy.
copies[node] = new ListNode(node.val). The copy's pointers stay unset for now, because its targets might not exist yet. Assigning through the indexer adds the key if it is new. - Move to the next original node. Without this the loop never ends.
- Reset the cursor to
headfor the second pass. - Loop again over the originals.
- Wire
next. The copy'snextis the copy ofnode.next, ornullif there is no next node. The conditional guards the lookup because aDictionarythrows anArgumentNullExceptionwhen you pass it a null key. - Wire
random. Same pattern withnode.random. - Advance along the original list's
nextpointers. The copies' links are what this loop is building, so they're not used for walking. - Return the copy of
head, guarded for an empty list, where looking upheadwould be a lookup with a null key.
The solution in C#
class Solution {
public ListNode CopyRandomList(ListNode head) {
Dictionary<ListNode, ListNode> copies = new Dictionary<ListNode, ListNode>();
ListNode node = head;
while (node != null) {
copies[node] = new ListNode(node.val);
node = node.next;
}
node = head;
while (node != null) {
copies[node].next = node.next != null ? copies[node.next] : null;
copies[node].random = node.random != null ? copies[node.random] : null;
node = node.next;
}
return head != null ? copies[head] : null;
}
}
Some C# details are worth a closer look:
- Reference keys. Class instances use reference equality by default, which is what you want here. A class that overrides
Equalsto compare values would break this approach for duplicate values like the 3, 3, 3 in the third example. - The indexer reads and writes.
copies[node] = …inserts or overwrites.copies[node]on the right-hand side reads, and throws aKeyNotFoundExceptionif the key is missing. Here every original node is a key by the second pass, so reads always succeed. - The conditional operator.
a != null ? copies[a] : nullevaluates only the branch it picks, socopies[null]is never executed. The line readscopies[node].next = (node.next != null) ? … : null, because=has lower precedence than?:. - Namespaces.
Dictionarylives inSystem.Collections.Generic, so a standalone file needsusing System.Collections.Generic;at the top. - Assigning
nullto a reference. BecauseListNodeis a class,nullis a valid value for its variables and for thenextandrandomfields.
Complexity
Time: O(n). Each pass visits every node once, and a dictionary insert or lookup takes constant time on average.
Space: O(n). The dictionary holds one entry per node, on top of the n new nodes that make up the output.
Edge cases and common mistakes
- Empty list. With
head == nullboth loops are skipped, and the final conditional returnsnullwithout touching the dictionary. - Random pointer to itself. A node whose
randompoints at the node itself must get a copy that points at itself, not at the original. The dictionary does this, because it looks up the node's own copy. - Random pointer forward or backward. That is why the pointers wait for the second pass. In a single pass, a node's
randommay point to a node that has no copy yet. - Equal values. The third example has three nodes with value 3. Keying a dictionary by value would merge them. Keying by node does not.
- Looking up null.
copies[node.random]with a nullrandomthrows anArgumentNullException, so keep the null check. - Pointing at originals. Writing
copy.random = node.randomwould make the copy share nodes with the original list, which the problem forbids. - Losing the cursor. If the first loop moves
headinstead ofnode, the second pass has nowhere to start.
Testing
[[7,null],[13,0],[11,4],[10,2],[1,0]]copies to the same pairs, with every pointer inside the new list.[[1,1],[2,1]]copies to[[1,1],[2,1]]: both random pointers go to the second node.[[3,null],[3,0],[3,null]]copies to the same pairs.[]returnsnull.
To confirm the copy is deep, check that no node of the result is a node of the input: ReferenceEquals(copyNode, originalNode) must be false for every pair.