LESSON 308 OF 414 · LINKED LISTS

Copy List with Random Pointer in Scala: O(n) Time with a HashMap

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 null.

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 null 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 (null), so return null.

Constraints:

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

Note:

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

STEP 1 OF 11

Guided

Ctrl + Enter to check

Copy List Random Pointer in Scala, explained

Problem overview

The method copyRandomList receives the head of a linked list of ListNode objects. Each node has a value, a next pointer and a random pointer, which may point to any node of the list or to null. The method must build a deep copy: exactly n brand-new nodes with the same values, where the new nodes' next and random pointers lead to new nodes and never to nodes of the original list. It returns the head of the copy, or null for an empty list.

The examples write each node as [val, random_index]. In [[7,null],[13,0],[11,4],[10,2],[1,0]], the node holding 13 has its random pointer on index 0, the node holding 7. The copy must have the same shape: its second node holds 13 and its random pointer goes to the copy's own first node, not the original one. The statement asks for O(n) time and at most O(n) extra space, and the list has up to 1000 nodes.

Approach: map every original node to its copy

Copying values and next links is easy: walk the list and create nodes. The difficulty is the random pointer. A random pointer can point forward or backward, so when you create a copy you may not have created its target yet.

The fix is to separate creation from wiring. First create every copy, remembering which original it belongs to in a map from original node to copy node. After this pass, every original has a copy. Then walk the original list again and, for each node, look up its copy and set the copy's next to the copy of node.next and the copy's random to the copy of node.random. Both lookups work because every copy already exists.

The map's keys must be the nodes themselves, compared by reference. Two different nodes can hold the same value, and a map keyed by value would mix them up.

Step by step

Create the map. val copies = scala.collection.mutable.HashMap[ListNode, ListNode]() maps each original to its copy. It is a val because the reference to the map never changes, while the map's contents do. The full package name is written because nothing is imported.
Create the walker, var node = head, so head itself stays untouched for later.
First pass: loop while node != null.
Store a copy with copies(node) = ListNode(node.`val`). Only the value is copied now. The backticks are needed because val is a Scala keyword.
Advance with node = node.next. Without it the loop never ends.
Go back to the start with node = head, since the first pass left node at the end.
Second pass: loop while node != null again.
Wire next. The copy's next is null when the original has no successor, otherwise the copy of that successor. An if/else expression is needed because copies(null) would fail.
Wire random with the same kind of expression.
Advance along the original list with node = node.next.
Return the copy of the head: if (head == null) null else copies(head). An empty list has no head to look up.

The solution in Scala

class Solution {
    def copyRandomList(head: ListNode): ListNode = {
        val copies = scala.collection.mutable.HashMap[ListNode, ListNode]()
        var node = head
        while (node != null) {
            copies(node) = ListNode(node.`val`)
            node = node.next
        }
        node = head
        while (node != null) {
            copies(node).next = if (node.next == null) null else copies(node.next)
            copies(node).random = if (node.random == null) null else copies(node.random)
            node = node.next
        }
        if (head == null) null else copies(head)
    }
}

The Scala details worth knowing:

Mutable versus immutable maps. Scala's default Map is immutable. The lesson uses scala.collection.mutable.HashMap, whose contents can be changed in place.
copies(node) = x is update. The assignment syntax calls copies.update(node, x), which adds or replaces the entry.
copies(key) throws for a missing key. Applying a map to a key that is absent throws NoSuchElementException. That is why null pointers are checked before the lookup. copies.get(key) would return an Option instead, and getOrElse gives a default.
Reference keys. The map hashes and compares its keys with hashCode and equals. For a plain class these are identity-based, so each node is its own key, even when two nodes hold the same value. This is what the algorithm needs. A class that overrides equals by contents would make nodes with equal contents collide.
if/else as an expression. Scala has no ternary operator. if (c) a else b produces a value, so it can be assigned to a field or returned as the last expression.
Calling the constructor without new. ListNode(node.`val`) works in Scala 3.
The last expression is the result, so there is no return.

Complexity

Time: O(n). Each pass visits every node once, and each map insertion or lookup takes constant time on average.

Space: O(n). The map holds one entry per node, and the copies themselves take n new nodes, which the result needs anyway. The statement allows O(n) extra space.

Edge cases and common mistakes

Empty list. Neither loop runs, and the final if returns null. Writing copies(head) without the check would throw.
A null random pointer. The first example's first node has none. Looking up null in the map would throw, so the check comes first.
Random pointing to the node itself or backward. Because all copies exist before any wiring, forward, backward and self pointers are all handled the same way.
Wiring in the first pass. A copy's target may not exist yet. Two passes avoid that.
Pointing the copy at an original node. Writing copies(node).random = node.random would leave the copy sharing nodes with the original, which breaks the deep copy.
Equal values. [[3,null],[3,0],[3,null]] has three nodes holding 3. The map is keyed by node, so each gets its own copy.
Forgetting to reset node. The second loop would not run at all, because node is already null.

Testing

[[7,null],[13,0],[11,4],[10,2],[1,0]] gives the same list, built from new nodes.
[[1,1],[2,1]] gives [[1,1],[2,1]].
[[3,null],[3,0],[3,null]] gives [[3,null],[3,0],[3,null]].
[] gives null, the empty list.

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

Start learning free