Clone a linked list with next and random pointers

Medium

Problem

Each node has next and a random pointer that points to any node in the list, or to null. Create a deep copy: new nodes whose next and random pointers point to the new nodes in the matching positions.

Example 1

Input:  [[7,null], [13,0], [11,4], [10,2], [1,0]]  (value, random index)
Output: An identical structure made of new nodes

Also asked as: Clone a linked list with next and random pointer

Test cases

Case 1

Input:    [[7,null],[13,0],[11,4],[10,2],[1,0]]
Expected: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Case 2

Input:    [[1,1],[2,1]]
Expected: [[1,1],[2,1]]

Case 3

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Interleave copies, wire randoms, split — O(1) space

Time O(n)Space O(1)

Insert each copy right after its original. Then copy.random = original.random.next. Finally unweave the two lists.

function copyRandomList(head) {
if (!head) return null;
for (let n = head; n; n = n.next.next) {
n.next = { val: n.val, next: n.next, random: null };
}
for (let n = head; n; n = n.next.next) {
if (n.random) n.next.random = n.random.next;
}
const copyHead = head.next;
for (let n = head; n; n = n.next) {
const c = n.next;
n.next = c.next;
c.next = c.next ? c.next.next : null;
}
return copyHead;
}

Simpler O(n) space: a Map from original node → copy node, two passes.