LESSON 285 OF 348 · LINKED LISTS

Copy List with Random Pointer in Kotlin: O(n) Time, O(1) Extra Space

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 O(1) extra space.

STEP 1 OF 22

Guided

Ctrl + Enter to check

Copy List Random Pointer in Kotlin, explained

Problem overview

Each ListNode has a val, a next pointer and a random pointer that can point at any node of the list or at nothing. The function copyRandomList receives the head and returns the head of a deep copy: n brand-new nodes with the same values, where every pointer of the copy leads to a node of the copy and none leads back into the original. The original list must be left as it was.

In the statement's notation, [[7,null],[13,0],[11,4],[10,2],[1,0]] describes five nodes. The node 13 has its random pointer on index 0, the node 7. The copy must have the same shape. An empty list gives null.

Approach: weave each copy into the list

The usual solution keeps a hash map from each original node to its copy, which costs O(n) extra memory. This lesson does without the map by using the list itself to remember which copy belongs to which original. The idea has three passes:

Interleave. Put a copy of every node directly after the node it copies. The list A -> B -> C becomes A -> A' -> B -> B' -> C -> C'.
Set the random pointers. If A.random is X, the copy of X is simply X.next, so A'.random = A.random.next. No map is needed.
Separate. Unweave the two lists, restoring the original and building the copy's own next chain.

The new nodes only ever need a position, not a lookup, so the extra memory is just the copy itself.

Step by step

Handle the empty list. If head is null, return null. Later steps read head.next, which would fail otherwise.
Declare var node: ListNode? = head with the type written out. After the guard, head is known to be non-null, but node will hold null once the walk passes the last node, so the variable is declared as nullable.
First pass: loop while node is not null.
Save the successor in nextNode, because inserting the copy overwrites node.next.
Create copyNode with the value of node. The random pointer isn't set yet.
Splice it in: node.next = copyNode, then copyNode.next = nextNode.
Jump to nextNode, not to node.next. The latter is the copy just inserted, and the loop would keep making copies of copies forever.
Reset node = head for the second pass.
Second pass: loop over the originals. Each node.next is its copy, so take it as copyNode.
If node.random is set, assign copyNode.random = node.random.next, the copy of the target.
Jump over the copy: node = copyNode.next, the next original.
Keep newHead = head.next before the third pass, since that pass rewires head.next.
Third pass: reset node = head, then for each original take copyNode = node.next and nextNode = copyNode.next (the next original) before rewiring anything.
Link the copies: if nextNode exists, copyNode.next = nextNode.next, the copy that follows it.
Restore the original: node.next = nextNode, then advance node = nextNode.
Return newHead.

The solution in Kotlin

class Solution {
    fun copyRandomList(head: ListNode?): ListNode? {
        if (head == null) {
            return null
        }
        var node: ListNode? = head
        while (node != null) {
            val nextNode = node.next
            val copyNode = ListNode(node.`val`)
            node.next = copyNode
            copyNode.next = nextNode
            node = nextNode
        }
        node = head
        while (node != null) {
            val copyNode = node.next
            if (node.random != null) {
                copyNode!!.random = node.random!!.next
            }
            node = copyNode!!.next
        }
        val newHead = head.next
        node = head
        while (node != null) {
            val copyNode = node.next
            val nextNode = copyNode!!.next
            if (nextNode != null) {
                copyNode.next = nextNode.next
            }
            node.next = nextNode
            node = nextNode
        }
        return newHead
    }
}

The Kotlin details worth knowing:

The declared type ListNode?. It states that node can be null, which is how every loop here ends. Kotlin 2.1 would infer the same type from head, but spelling it out removes any doubt about the smart cast that follows the guard.
Mutable properties aren't smart-cast. node.random is a var property, so after node.random != null the compiler still treats it as nullable, and node.random!!.next needs the assertion. A local val such as nextNode is smart-cast after its own check.
copyNode!!. node.next is typed as nullable, but after the first pass every original has a copy after it, so the assertion holds. After copyNode!!.next succeeds once, Kotlin smart-casts the local val copyNode to non-null for the rest of that iteration.
Several val copyNode declarations. Each is local to its own loop body, so the same name can be reused in all three loops.
Backticks for val. The field is written node.`val`.

Complexity

Time: O(n). Each of the three passes visits each node a constant number of times.

Space: O(1) extra, apart from the n nodes of the copy, which the output requires. There is no map, no recursion and no per-node storage beyond a few pointers.

Edge cases and common mistakes

Empty list. The guard returns null immediately.
Single node pointing at itself. For [[1,0]], the node's random is the node itself, so the copy's random is node.next, which is the copy. The result is a one-node list whose random points at itself.
A null random. The check on node.random leaves the copy's pointer as null, instead of calling .next on null.
Not restoring the original. If the third pass doesn't reset node.next, the caller's list stays interleaved with the copies.
Reading head.next after the third pass. It has been restored to the original second node, so take newHead before.
Doing the random pass and the split in one pass. Splitting early would remove copies that later random pointers still need to find.

Testing

[[7,null],[13,0],[11,4],[10,2],[1,0]] gives the same pairs, made of new nodes, with the original list unchanged.
[[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