Problem overview
Each node of a linked list has a val, a next link and a random link that can point to any node of the list or to nothing. In this course a link is Option<Rc<RefCell<ListNode>>>, written Link. The function copy_random_list receives the head and must return the head of a deep copy: exactly n new nodes with the same values, where every next and random link of the copy points to nodes of the copy, never to the original.
Take the list [[7,null],[13,0],[11,4],[10,2],[1,0]], where each pair is the value and the index of the random target. The node 13 has its random link pointing back to the node 7, the first node. In the copy, the new 13 must point to the new 7, not to the old one. An empty list returns None.
Approach: map every original node to its copy
Copying the values and the next links is easy: walk the list and build new nodes. The hard part is random. When you create the copy of a node, its random target may be a node further down the list that has no copy yet, or one you have already passed.
The way out is two passes. The first pass creates one copy for every original node and records the pairing in a hash map from original to copy. The second pass wires the links: for each original node, look up its copy, then look up the copies of its next and random targets in the same map. Since every copy exists by then, every lookup succeeds.
The map uses the node's address as its key, not its value. The lesson's third example, [[3,null],[3,0],[3,null]], has three nodes with the same value. A map keyed by value would mix them up, but their addresses are always different. Rc::as_ptr gives that address.
The cost is O(n) time and O(n) extra space for the map. A different lesson on this problem trades the map away for an interleaving trick that needs O(1) extra space.
Step by step
- Create the map.
copiesis a mutableHashMap::new(). You don't write its types: Rust infers them from the firstinsert. - Create the cursor.
nodestarts ashead.clone(). Cloning anRccopies the pointer, not the node, and leavesheadavailable for the second pass. - Loop over the originals with
while let Some(curr) = node. - Create the copy. Insert into
copies, under the keyRc::as_ptr(&curr), a new node made byListNode::new(curr.borrow().val). Only the value is copied for now. - Advance. The pattern moved the value out of
node, so assignnode = curr.borrow().next.clone()before the loop tests it again. - Write a lookup closure.
copy_oftakes a&Linkof the original list and returns the matching link of the copy.link.as_ref().map(...)keepsNoneasNone, and for a nodexit finds the copy by address and clones theRc. - Restart the cursor with
node = head.clone(). - Loop again over the originals, naming the node
curr. - Find the copy of
currwith&copies[&Rc::as_ptr(&curr)]. - Wire
next. Set the copy'snexttocopy_of(&curr.borrow().next). - Wire
randomthe same way fromcurr.borrow().random. - Advance along the original list.
- Return
copy_of(&head): the copy of the head, orNonefor an empty list.
The solution in Rust
// The list node, already defined in the program:
// struct ListNode {
// val: i32,
// next: Link,
// random: Link,
// }
// type Link = Option<Rc<RefCell<ListNode>>>;
// ListNode::new(val) makes a new node, an Rc<RefCell<ListNode>>, whose next and random are None.
impl Solution {
fn copy_random_list(head: Link) -> Link {
let mut copies = HashMap::new();
let mut node = head.clone();
while let Some(curr) = node {
copies.insert(Rc::as_ptr(&curr), ListNode::new(curr.borrow().val));
node = curr.borrow().next.clone();
}
let copy_of = |link: &Link| link.as_ref().map(|x| copies[&Rc::as_ptr(x)].clone());
node = head.clone();
while let Some(curr) = node {
let copy = &copies[&Rc::as_ptr(&curr)];
copy.borrow_mut().next = copy_of(&curr.borrow().next);
copy.borrow_mut().random = copy_of(&curr.borrow().random);
node = curr.borrow().next.clone();
}
copy_of(&head)
}
}
Rust details worth noticing:
RcandRefCell. Several links can point to the same node, so nodes are shared withRc, a reference-counted pointer.RefCellallows changing a node through a shared pointer:borrow()reads it andborrow_mut()writes it, with the rules checked while the program runs.- Keys by address.
Rc::as_ptr(&curr)returns a raw pointer, which can be hashed and compared. TwoRchandles to the same node give the same pointer. Clones made withclone()don't change it. - Borrow timing. The line
copy.borrow_mut().next = copy_of(&curr.borrow().next);borrows two different nodes, the copy for writing and the original for reading. That is fine. Borrowing the same node mutably and immutably at once would panic when the program runs, not stop the compiler. - The closure and the map.
copy_ofborrowscopieswithout changing it, which is why all inserts come before it. Indexing withcopies[&key]panics if the key is missing, and here every node of the list has been inserted. - The list is left as it was. The function reads the original nodes and writes only to the copies.
- Cycles. A random link that points back at an earlier node, or at the node itself, creates a cycle of
Rcpointers.Rccounts can't free cycles, so such nodes stay in memory when the program doesn't break the links.
Complexity
Time: O(n). The first pass visits each node once with a constant-time insert. The second pass visits each node once with constant-time lookups. Hashing a pointer takes constant time.
Space: O(n) extra. The map holds one entry per node. The copied list itself is also n nodes, but that is the output.
Edge cases and common mistakes
- An empty list. Both loops are skipped, and
copy_of(&head)returnsNone. - Random pointing to itself. For
[[5,0]], the copy's random points to the copy, because the lookup returns the node's own copy. - Random pointing forward or backward. The second pass makes the direction irrelevant, since every copy already exists.
- Equal values. Keying the map by value would give all three 3s the same copy. Keying by address keeps them apart.
- Sharing nodes with the original. If you set
copy.random = curr.random.clone(), the copy would point into the original list, which breaks the deep copy. - Creating copies and wiring links in one pass. A random target further down the list has no copy yet at that moment.
- Forgetting to advance
node. Becausewhile letmoves the value out, the compiler stops you from usingnodeagain without assigning it first.
Testing
[[7,null],[13,0],[11,4],[10,2],[1,0]]gives the same list, in new nodes.[[1,1],[2,1]]gives[[1,1],[2,1]].[[3,null],[3,0],[3,null]]gives[[3,null],[3,0],[3,null]].[[5,0]]gives[[5,0]].[]gives[].
