138. Copy List with Random Pointer

At a Glance

• Topic: linked-list
• Pattern: Hash map / interleaving clone
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 138

Problem (one-liner)

Each node has Next and Random (may point anywhere or nil). Deep-copy the graph-shaped list so all pointers refer to nodes in the new list with identical structure.

Recognition Cues

• Random pointer on linked nodes
• Deep copy with cycles allowed only as structure replication
• Two classics: map old→new, or interleave clones then split

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n) time / O(n) space — DFS + map for visited clones (fine).
• Better — O(n) time / O(n) space — one pass: allocate clones lazily in map, wire Next and Random in second pass.
• Optimal — O(n) time / O(1) extra beyond output — interleave cloned node after each original, assign random on clones, then unzip.

Optimal Solution

Go

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	current := head
	for current != nil {
		clone := &Node{Val: current.Val, Next: current.Next}
		current.Next = clone
		current = clone.Next
	}
	current = head
	for current != nil {
		clone := current.Next
		if current.Random != nil {
			clone.Random = current.Random.Next
		}
		current = clone.Next
	}
	dummy := &Node{}
	tail := dummy
	current = head
	for current != nil {
		clone := current.Next
		nextOriginal := clone.Next
		tail.Next = clone
		tail = clone
		current.Next = nextOriginal
		current = nextOriginal
	}
	return dummy.Next
}

JavaScript

class Node {
	constructor(val = 0, next = null, random = null) {
		this.val = val;
		this.next = next;
		this.random = random;
	}
}

function copyRandomList(head) {
	if (head === null) {
		return null;
	}
	let current = head;
	while (current !== null) {
		const clone = new Node(current.val, current.next, null);
		current.next = clone;
		current = clone.next;
	}
	current = head;
	while (current !== null) {
		const clone = current.next;
		if (current.random !== null) {
			clone.random = current.random.next;
		}
		current = clone.next;
	}
	const dummy = new Node();
	let tail = dummy;
	current = head;
	while (current !== null) {
		const clone = current.next;
		const nextOriginal = clone.next;
		tail.next = clone;
		tail = clone;
		current.next = nextOriginal;
		current = nextOriginal;
	}
	return dummy.next;
}

Walkthrough

Original A -> B, A.random = B.

Invariant: clone sits immediately after its original until unzip completes.

Edge Cases

• Empty list.
• random nil for all nodes.
• Singleton node self-referenced randomly.

Pitfalls

• Map-based forgetting second pass for Random when nodes created lazily.
• Interleaving method losing original links before unzip — follow clone.Next carefully.

Similar Problems

• 133. Clone Graph — same old→new mapping idea on a general graph.
• 21. Merge Two Sorted Lists — careful relinking of Next under mutation.
• 143. Reorder List — in-place rewiring of a singly linked structure.

Variants

• Hashmap two-pass — often easier in interview if O(n) space is acceptable.
• Deep copy with cycles — map essential; interleaving handles list-shaped cases cleanly.

Mind-Map Tags

#linked-list #deep-copy #random-pointer #interleave-unzip