Problem overview
The function copyRandomList receives the head of a linked list of *ListNode values. Each node has Val, Next and a Random pointer that may point to any node of the list or be nil. The function returns the head of a deep copy: n new nodes with the same values, whose Next and Random pointers point only to other new nodes. The original list must keep its structure.
For the list [[7,null],[13,0],[11,4],[10,2],[1,0]], written as [val, random_index] pairs, the copy has the same five pairs, but it consists of new nodes. An empty list gives nil. This version must run in O(n) time and use O(1) extra space, which rules out a map from originals to copies.
Approach: weave each copy in after its original
The map-based solution answers the question "which node is the copy of X?" with a lookup table. The constant-space solution stores the answer in the list itself. It inserts each copy directly after its original, so the copy of X is always X.Next:
A -> B -> C becomes A -> A' -> B -> B' -> C -> C'Then the whole job takes three passes:
- Interleave. After each original node, insert a copy that holds the same value.
- Set the random pointers. If an original
nodehasnode.Random, then its copy isnode.Next, and its random target's copy isnode.Random.Next. Sonode.Next.Random = node.Random.Next. - Separate. Unweave the two lists: restore each original's
Next, and chain the copies to one another. The input is restored exactly as it was.
The extra memory is just a few pointers, because the n new nodes are the output.
Step by step
- Handle the empty list. If
head == nil, returnnil. The code later readshead.Next. - Start the first loop with
for node := head; node != nil; {. The post statement is empty, since the body movesnodeitself. - Save
next := node.Next. The next step overwrites that link. - Build the copy with its value and its
Nextalready set:copy := &ListNode{Val: node.Val, Next: next}. It slots into the chain in one step, and itsRandomstarts asnil. - Splice it in:
node.Next = copy. - Jump over the copy:
node = next. Moving tonode.Nextwould land on the copy and insert copies of copies forever. - Start the second loop over the originals. The post statement
node = node.Next.Nexthops two nodes, from original to original. This is safe because every original is followed by its copy. - Check
node.Random != nil. Copies of nodes without a random target already have anilone. - Set the copy's random:
node.Next.Random = node.Random.Next. The node after the target is the target's copy. - Save the answer before the lists are separated:
newHead := head.Next, the first copy. - Start the third loop, again over the originals with an empty post statement.
- Take the copy of the current node:
copy := node.Next. - Save the next original,
next := copy.Next, before any link is rewired. - Restore the original list:
node.Next = next. - Check
next != nil. The last copy has no following copy, and itsNextis alreadynil. - Chain the copies:
copy.Next = next.Next. The node afternextisnext's copy. - Advance with
node = next. - Return
newHead.
The solution in Go
func copyRandomList(head *ListNode) *ListNode {
if head == nil {
return nil
}
for node := head; node != nil; {
next := node.Next
copy := &ListNode{Val: node.Val, Next: next}
node.Next = copy
node = next
}
for node := head; node != nil; node = node.Next.Next {
if node.Random != nil {
node.Next.Random = node.Random.Next
}
}
newHead := head.Next
for node := head; node != nil; {
copy := node.Next
next := copy.Next
node.Next = next
if next != nil {
copy.Next = next.Next
}
node = next
}
return newHead
}
Go details worth knowing:
- Loop variables belong to the loop.
nodeis declared in eachforstatement's init part and exists only inside that loop, so each of the three loops declares its own. - The init-only
for.for node := head; node != nil; {has an empty post statement. That is legal, and the body advancesnodeitself, which the first and third loops need because they don't step tonode.Next. - A variable named
copy. Go has a built-in functioncopyfor slices. Declaring a variable with that name shadows it inside the loop body. That is harmless here, since the built-in isn't used, but it's a name to avoid in code that also copies slices. - Composite literal with several fields.
&ListNode{Val: node.Val, Next: next}sets two fields by name and leavesRandomasnil.
Complexity
Time: O(n). Each of the three loops visits every original node once, and the work per node is constant.
Space: O(1) extra. There is no map and no slice. The only memory beyond the n required copies is a handful of pointer variables. The interleaving temporarily doubles the length of the original list, and the third pass undoes it.
Edge cases and common mistakes
- Empty list. The guard at the top returns
nil. Without it,head.Nextwould panic. - Doing the passes in the wrong order. The random pointers must be set before the lists are separated. After separation,
node.Random.Nextno longer leads to a copy. - Not restoring the original. The caller still owns the input list. If the third pass is skipped or left half done, the original stays interleaved with the copies.
- Reading
node.Random.NextwhenRandomisnil. The check onnode.Randomprevents a nil pointer dereference. - Losing the last copy's end. For the last original,
nextisnil, sonext.Nextmust not be read. The check protects this, and the copy'sNextisnilalready. - Advancing to
node.Nextin the first loop. That visits the copy just inserted and makes copies of copies without end. - Setting a random pointer to the original's target.
node.Next.Random = node.Randomwould leave the copy pointing into the original list.
Testing
[[7,null],[13,0],[11,4],[10,2],[1,0]]gives the same five pairs, on new nodes. The original list still has its five nodes in order afterwards.[[1,1],[2,1]]gives[[1,1],[2,1]].[[3,null],[3,0],[3,null]]gives[[3,null],[3,0],[3,null]].[]gives[].