Start learning free

LESSON 284 OF 348 · LINKED LISTS

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

Practice O(n) Read the full explanation

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 representing Node.val
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 pointer), so return null.

Constraints:

0 <= n <= 1000
-10000 <= Node.val <= 10000
Node.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

KOTLIN · LINKED LISTS

Copy List Random Pointer in Kotlin, explained

Problem overview

Each ListNode in the input has a val, a next pointer and an extra random pointer, which may point at any node of the list or be null. The function copyRandomList 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 of the copy points to a node of the copy, never to a node of the original.

The statement writes a list as pairs [val, random_index]. In [[7,null],[13,0],[11,4],[10,2],[1,0]], the node 13 has its random pointer on node index 0, which is the node 7. The copy must have the same shape: its second node's random must be the copy's first node. An empty list gives null.

The statement allows O(n) time and O(n) extra space.

Approach: map every original node to its copy

Copying the values and the next chain is easy. The difficulty is the random pointers: when you create a copy, the node its random pointer targets might not be copied yet, and it may be far away from the current node. You need a way to ask, for any original node, "which node is its copy?"

A hash map answers that question in constant time. The plan has two passes:

Walk the list and create a copy of each node, with only its value set. Store the pair original to copy in the map.
Walk the list again. Now every original has a copy, so for each node you can look up the copy of next and the copy of random and wire them into the node's own copy.

Splitting the work into two passes removes the ordering problem: by the second pass, every lookup succeeds.

Step by step

Create the map as a val copies of type HashMap<ListNode?, ListNode?>. The map itself is never reassigned, but its contents change. Making the key type nullable means copies[node.next] compiles when node.next is null, and it simply returns null.
Start a walker as var node = head, so that head is still available for the second pass and the return.
Loop while node is not null.
Store a new node under the key node, built with ListNode(node.`val`). Only the value is copied now. The targets of next and random may not have copies yet.
Advance with node = node.next. Without it the loop never ends.
Reset with node = head, because the first loop left the walker at the end.
Loop again over the originals.
Wire next: copies[node]!!.next = copies[node.next]. The copy of the current node is found with copies[node]!!, and the copy of its successor with copies[node.next]. For the last node that lookup gives null, which ends the copied chain.
Wire random the same way, with copies[node.random].
Advance along the original list.
Return copies[head], the copy of the head. For an empty list it is null.

The solution in Kotlin

class Solution {
    fun copyRandomList(head: ListNode?): ListNode? {
        val copies = 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 = copies[node.next]
            copies[node]!!.random = copies[node.random]
            node = node.next
        }
        return copies[head]
    }
}

The Kotlin details worth knowing:

Keys compare by identity here. A HashMap uses equals and hashCode of its keys. A plain class that doesn't override them inherits the versions that compare by reference, so two nodes with equal values are still different keys. If ListNode were a data class, whose equals compares fields, nodes with equal contents could be treated as the same key.
map[key] returns a nullable. Reading from a map gives V?, which is null for a missing key. Because the value type is already ListNode?, the result of copies[node.next] can be assigned to next, which is also ListNode?, without any conversion.
!! after copies[node]. The lookup returns a nullable, and the compiler can't know that every original was stored in the first pass. !! asserts it; if the value were null, it would throw a NullPointerException. Here it never is.
Backticks for val. The field is named like a keyword, so it is written node.`val`.
Smart cast. Inside while (node != null), the local var node counts as non-null, so node.next and node.random need no ?..
Reusing node. The variable is inferred as ListNode? from head, so assigning node = head for the second pass is allowed.

Complexity

Time: O(n). There are two passes over the list. Each step does a constant number of hash map operations, which take constant time on average.

Space: O(n). The map holds one entry per node, and the copy itself has n new nodes. Both are linear.

Edge cases and common mistakes

Empty list. The loops never run and copies[head] is null, so the function returns null.
Random pointer to itself or to an earlier node. Both are fine, because all copies exist before any pointer is wired. [[1,1],[2,1]] gives the same shape back, with both random pointers on the second node.
Equal values. In [[3,null],[3,0],[3,null]] every node holds 3. The map must be keyed by the node, not by its value, or the copies would be confused.
Linking to the original. Assigning node.next or node.random to the copy would make the new list point into the old one, which the statement forbids.
Wiring in the first pass. The target of a pointer might not have a copy yet, so the lookup would give null for a pointer that should be set.
Forgetting to reset node. After the first loop the walker is null, so the second loop would do nothing and every copy would have null pointers.

Testing

[[7,null],[13,0],[11,4],[10,2],[1,0]] gives a list with the same pairs, made of new nodes.
[[1,1],[2,1]] gives [[1,1],[2,1]].
[[3,null],[3,0],[3,null]] gives the same pairs.
An empty list gives null.

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

Start learning free