Copy List with Random Pointer

Medium

The problem

Each node of a linked list has a val, a next pointer, and a random pointer that can point to any node in the list (or be nil). Make a deep copy: build brand-new nodes with the same values, where next and random point to the new nodes in the same pattern. No new node may point to an original node. Return the head of the copy.

Example 1
Input: head = [[1, 1], [2, 0], [3, null]] (each pair is [val, index of the node random points to])
Output: [[1, 1], [2, 0], [3, null]]
The copy has the same values and the same random links, but all three nodes are new. Node 1's random points at the 2nd node, node 2's random points back at the 1st, and node 3's random is nil.
Example 2
Input: head = [[5, 0]]
Output: [[5, 0]]
The only node's random points to itself, so the copy's random must point to the copy itself.

Limits

0 ≤ number of nodes ≤ 1,000
-10,000 ≤ node value ≤ 10,000
random is nil or points to a node in the same list

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A random pointer points at some other node. How do you find that node's copy?

The idea

First pass: map each original node → its new copy. Second pass: wire copy.next and copy.random through the map.

Target: O(n) time, O(n) space

Go function shape

func copyRandomList(head *Node) *Node

Reference solution

Tested with go test. Try it yourself first, then compare.

// RandomNode is a list node with an extra pointer to any node in the list (or nil).
type RandomNode struct {
	Val          int
	Next, Random *RandomNode
}

// CopyRandomList makes a deep copy. First pass: create one copy per original and remember original→copy
// in a map. Second pass: wire the copies' Next and Random through that map.
func CopyRandomList(head *RandomNode) *RandomNode {
	copies := map[*RandomNode]*RandomNode{nil: nil} // nil maps to nil so end-of-list needs no special case
	for n := head; n != nil; n = n.Next {
		copies[n] = &RandomNode{Val: n.Val}
	}
	for n := head; n != nil; n = n.Next {
		copies[n].Next = copies[n.Next]
		copies[n].Random = copies[n.Random]
	}
	return copies[head]
}

Read the lesson: Linked List · Fast & Slow Pointers