AlgoViz
HomeLinked List

Clone a LL with random and next pointer

Hard

Weave copies in, then split them out

Problem

Given the head of a special linked list of n nodes where each node contains an additional pointer called 'random' which can point to any node in the list or null. Construct a deep copy of the linked list where, n new nodes are created with corresponding values as original linked list. The random pointers point to the corresponding new nodes as per their arrangement in the original list. Return the head of the newly constructed linked list. Note: For custom input, a n x 2 matrix is taken with each row having 2 values:[ val, random_index] where, val: an integer representing ListNode.val random_index: index of the node (0 - n-1) that the random pointer points to, otherwise -1.

In simple words

Slip a copy behind each node, wire up the random arrows, then peel the copies off.

The idea

Insert each copied node directly after its original, so a copy's random pointer is simply original.random.next. Then unweave the two lists. That interleaving trick replaces the hash map from original to copy with O(1) space.

The trick

  • Three passes: weave, set randoms, unweave.
  • copy.random = original.random.next — the whole reason for weaving.
  • Restore the original list's next pointers when you split.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
-1
0
1

Step 1 of 2. Here's the example — [[1, -1], [2, 0], [3, 4], [4, 1], [5, 2]] Values: 1, -1.

1/2
Optimal
timeO(n)spaceO(1)
1// 1. insert copy after each node2// 2. copy.random = orig.random.next3// 3. detach the copies into their own list4return clonedHead

Input

array
[1, -1]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
[[1, -1], [2, 0], [3, 4], [4, 1], [5, 2]]
Output:
1 2 3 4 5, true
Explanation:
All the nodes in the new list have same corresponding values as original nodes. All the random pointers point to their corresponding nodes in the new list. 'true' represents that the nodes and references were created new.

Example 2

Input:
[[5, -1], [3, -1], [2, 1], [1, 1]]
Output:
5 3 2 1, true
Explanation:
All the nodes in the new list have same corresponding values as original nodes. All the random pointers point to their corresponding nodes in the new list. 'true' represents that the nodes and references were created new. [[5, -1], [3, -1], [2, -1], [1, -1]] will be incorrect, although it has the same values.

Constraints

  • n == number of nodes in the linked list.
  • 1 <= n <= 10^5
  • -10^4 <= ListNode.val <= 10^4
  • 0 <= random_index < n or random_index == -1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.