LESSON 324 OF 445 · LINKED LISTS

Copy List with Random Pointer in Rust: O(1) Extra Space by Interleaving

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or None.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer, the value of the node
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or None if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (None), so return None.

Constraints:

0 <= n <= 1000
-10000 <= val <= 10000
random is None or is pointing to some node in the linked list.

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 22

Guided

Ctrl + Enter to check

Copy List Random Pointer in Rust, explained

Problem overview

A linked list node has a val, a next link and a random link that points to any node of the list or to nothing. A Link is Option<Rc<RefCell<ListNode>>>. The function copy_random_list receives the head and must return the head of a deep copy: n brand-new nodes with the same values, where every next and random link of the copy points inside the copy.

The input [[7,null],[13,0],[11,4],[10,2],[1,0]] lists each node as its value and the index of its random target. The copy must have the same shape, with the new 13 pointing to the new 7. An empty list gives None. This version must run in O(n) time and use O(1) extra space, so a map from originals to copies is not allowed.

Approach: weave each copy next to its original

The map in the other approach exists to answer one question: where is the copy of node X? The idea here is to make the answer a pointer you can follow. Put each copy directly after its original, so the list reads A, A', B, B', C, C'. Then the copy of any node X is simply X.next.

That gives three passes over the list:

Interleave. After each original node, insert a new node with the same value.
Set the random links. If an original A has A.random = C, then A'.random must be C', which is C.next. So A'.random = A.random.next. This works because every copy exists before this pass starts.
Separate. Unweave the two lists: rewire the originals to skip their copies, and the copies to skip the originals. This also restores the input list, which the caller still owns.

Try it on a two-node list where the first node's random points to the second. After pass 1 the chain is A, A', B, B'. In pass 2, A.random is B, and B's next is B', so A'.random becomes B'. Pass 3 leaves A, B as before and A', B' as a separate list, with the random link of A' inside it.

Step by step

Guard the empty list. If head.is_none(), return None. Later the code reads the first node's next, which would fail on an empty list.
Create the cursor node as head.clone(). Cloning an Rc copies the pointer, not the node.
First loop with while let Some(curr) = node, to insert a copy after every original.
Save the successor. Put curr.borrow().next.clone() in next_node. Inserting the copy overwrites curr's next link, and without the saved link the rest of the list would be lost.
Create the copy, copy_node, from curr.borrow().val. Its random link stays None for now.
Splice it in by setting curr.borrow_mut().next to Some(copy_node.clone()).
Chain it onward by setting the copy's next to the saved next_node.
Advance to next_node, not to curr's next, which is now the copy. This skips the copy just inserted.
Restart the cursor with node = head.clone().
Second loop, to set the random links. Here curr only visits originals.
Find the copy: curr.borrow().next.clone().unwrap(). After pass 1 it is always there.
Copy the random link when curr has one: set the copy's random to random.borrow().next.clone(), the node after the target, which is the target's copy.
Jump to the copy's next, the next original.
Save the new head as the node after head, read with head.as_ref().unwrap().borrow().next.clone(). Do it before the third pass changes head's next.
Restart the cursor once more.
Third loop, to separate the lists. In each pass take the copy after curr, then save the next original from the copy's next before anything is rewired.
Link the copies together. If there is a next original, set the copy's next to the copy that follows it.
Restore the original. Set curr's next to the saved next original, then advance to it.
Return new_head.

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 {
        if head.is_none() {
            return None;
        }

        let mut node = head.clone();
        while let Some(curr) = node {
            let next_node = curr.borrow().next.clone();
            let copy_node = ListNode::new(curr.borrow().val);
            curr.borrow_mut().next = Some(copy_node.clone());
            copy_node.borrow_mut().next = next_node.clone();
            node = next_node;
        }

        node = head.clone();
        while let Some(curr) = node {
            let copy_node = curr.borrow().next.clone().unwrap();
            if let Some(random) = curr.borrow().random.clone() {
                copy_node.borrow_mut().random = random.borrow().next.clone();
            }
            node = copy_node.borrow().next.clone();
        }

        let new_head = head.as_ref().unwrap().borrow().next.clone();
        node = head.clone();
        while let Some(curr) = node {
            let copy_node = curr.borrow().next.clone().unwrap();
            let next_node = copy_node.borrow().next.clone();
            if let Some(next) = &next_node {
                copy_node.borrow_mut().next = next.borrow().next.clone();
            }
            curr.borrow_mut().next = next_node.clone();
            node = next_node;
        }

        new_head
    }
}

Rust details worth noticing:

Shared, mutable nodes. Rc lets several links own the same node, and RefCell lets you change it through a shared handle: borrow() to read, borrow_mut() to write. The borrow rules are checked while the program runs.
Short borrows. Most borrow() calls here are temporaries that end with their statement. That is why curr.borrow_mut().next = Some(copy_node.clone()); is safe right after curr.borrow().next.clone(): the earlier read borrow is already gone. Each statement that holds two borrows holds them on different nodes, one to read and one to write.
if let and borrows. In if let Some(random) = curr.borrow().random.clone(), the temporary read borrow of curr lasts through the whole body. The body only writes to copy_node and reads random, so it never needs a write borrow of curr, and there is no conflict.
&next_node. if let Some(next) = &next_node matches on a reference, so next_node isn't moved and can be used after the if.
Reassigning node. while let Some(curr) = node moves the value out of node, so each pass must assign it a new value, and the code does so on its last line. In the third loop, node = next_node moves next_node, which is why the earlier uses clone it.
unwrap() calls. Each one is on a node that exists because pass 1 inserted a copy after every original.

Complexity

Time: O(n). Three passes, each visiting every node once with constant work per node.

Space: O(1) extra. Apart from the n copies that make up the output, the code keeps only a few Rc handles. No map, no vector and no recursion.

Edge cases and common mistakes

An empty list. The guard returns None before any loop runs.
A single node. The chain becomes A, A'. Pass 3 sees no next original, leaves the copy's next as None and sets A's next back to None.
Random pointing to itself. For [[5,0]], A.random is A and A's next is A', so A'.random becomes A'.
Advancing to curr's next in pass 1. That is the copy, so the loop would keep copying copies and never end.
Setting random links in pass 1. The target's copy may not exist yet. Do it in a pass of its own.
Reading the new head too late. After pass 3, head's next is the original second node, not the copy.
Not restoring the original. A copy that leaves the input list interleaved is wrong, since the caller still owns that list.
Rewiring before saving. In pass 3, read the next original from the copy before you change the copy's next.

Testing

[[7,null],[13,0],[11,4],[10,2],[1,0]] gives the same list in new nodes, and the input is unchanged.
[[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 [].

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free