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 that may point to any node in the list or to null. The method must return a deep copy: n new nodes with the same values, whose next and random pointers lead only to other new nodes. For an empty list it returns null.
The examples write a node as [val, random_index]. In [[1,1],[2,1]], both nodes have their random pointer on index 1, the node holding 2. The copy has the same shape, with both random pointers on the copy's second node. This lesson's note asks for O(n) time and only O(1) extra space, so storing a map from originals to copies is not allowed.
Approach: put each copy right after its original
The map in the usual solution answers one question: "which copy belongs to this original?" The same answer can be stored in the list itself. If every copy sits directly after its original, the copy of any node X is simply X.next, with no lookup table.
That leads to three passes:
- Interleave. Insert a copy after each original, turning
A → B → CintoA → A' → B → B' → C → C'. - Set random pointers. For an original with
randompointing atX, its copy'srandommust be the copy ofX, which isX.next. Socopy.random = node.random.next. - Separate. Unweave the two lists, restoring the original and linking the copies together. The caller still owns the original list and expects it unchanged.
The only new memory is the copies themselves, which the result needs anyway, so the extra space is O(1).
Step by step
- Guard the empty list. If
headisnull, returnnull. Later code readshead.next. - Create the walker,
var node = head. - First pass: loop while
node != null. - Save the original successor in
val nextNode = node.next, because inserting the copy overwritesnode.next. - Create the copy,
val copyNode = ListNode(node.`val`). Only the value is copied now. The backticks are needed becausevalis a Scala keyword. - Insert it by setting
node.next = copyNode. - Reconnect the chain with
copyNode.next = nextNode. - Skip the copy by moving to
nextNode. Moving tonode.nextwould land on the copy and create copies of copies without end. - Reset the walker to
headfor the second pass. - Second pass: loop while
node != null. Each iteration visits only originals. - Take the copy with
val copyNode = node.next. - Set its random pointer. If
node.randomis notnull, setcopyNode.random = node.random.next, the copy of the target. - Jump to the next original:
node = copyNode.next. - Remember the new head before the lists are separated:
val newHead = head.next. - Reset the walker to
headagain. - Third pass: loop while
node != null. - Read the pair:
val copyNode = node.next, and the next originalval nextNode = copyNode.next, before any link changes. - Link the copies: if
nextNodeis notnull, setcopyNode.next = nextNode.next. For the last copy,nextis alreadynull. - Restore the original with
node.next = nextNode. - Advance with
node = nextNode. - Return
newHeadas the last expression.
The solution in Scala
class Solution {
def copyRandomList(head: ListNode): ListNode = {
if (head == null) {
return null
}
var node = 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
}
newHead
}
}
The Scala details worth knowing:
returnonly for the early exit. The guard usesreturn nullto leave the method early, while the normal result is the last expression,newHead. Scala code usually avoidsreturn, but an early exit is the common case where it reads well.- Scoped
vals. Each loop body declares its owncopyNodeandnextNode. They are separate for each pass and each iteration, and they cannot be reassigned. var nodeis reused. The same variable walks all three passes, and each pass starts by assigningnode = head.- Fields are assignable.
node.next = copyNodechanges a field of an existing object, which is allowed even thoughnodeis the loop's walker. The list's structure, not the variable, is what changes. - Null checks.
nullis a validListNodevalue, so every dereference that might see it,node.random.nextandnextNode.next, is guarded.
Complexity
Time: O(n). Each of the three passes visits every original node once and does constant work per node.
Space: O(1) extra. Apart from the n new nodes, which are the output, the method uses a few references. No map or array is built.
Edge cases and common mistakes
- Empty list. The guard returns
nullbeforehead.nextis read. - Single node. The first pass makes
A → A', the second pass copies its random pointer if it has one, and the third pass leavesAwithnextofnullandA'as the new head. - Setting random pointers before interleaving is complete. The target's copy must already be in place, which is why this is a separate second pass.
- Splitting during the random pass. Unweaving too early destroys the
X.nexttrick for nodes that have not been handled yet. - Not restoring the original. If the third pass skipped
node.next = nextNode, the caller's list would still contain the copies. - Losing the new head. After the third pass
head.nextis the original second node again, sonewHeadmust be saved before it. - A
nullrandom pointer. Readingnode.random.nextwithout the check would throw aNullPointerException.
Testing
[[7,null],[13,0],[11,4],[10,2],[1,0]]gives the same list, built from new nodes, and the original is left as it was.[[1,1],[2,1]]gives[[1,1],[2,1]].[[3,null],[3,0],[3,null]]gives[[3,null],[3,0],[3,null]].[]givesnull.
