Clone a linked list with next and random pointers
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: []
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.