Copy List with Random Pointer Medium 0 attempts
LeetCode ↗

Copy List with Random Pointer

Medium Linked List LeetCode

You're given a linked list in which every node carries, besides its usual next pointer, an extra random pointer that can point to any node in the list or to nothing at all. Build a completely independent deep copy of this list, matching the same structure.

Input Format
Implement copyRandomList(head). Inputs below show JavaScript function arguments; there is no stdin parsing. Random lists use [value, randomIndex] pairs; null means no random pointer. The editor builds next and random references.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2

Input
head = []
Output
[]
Constraints
  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • random is null or points to a node in the list
Test Cases (2)
Case 1
Args: [[[7,null],[13,0],[11,4],[10,2],[1,0]]] Expected: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Case 2
Args: [[]] Expected: []
Topics
Linked List

Interleave + Separate

Insert cloned nodes after originals, set random pointers, then separate.

javascript
function copyRandomList(head) {
  if (!head) return null;
  let curr = head;
  while (curr) {
    const clone = {val: curr.val, next: curr.next, random: null};
    curr.next = clone; curr = clone.next;
  }
  curr = head;
  while (curr) { if (curr.random) curr.next.random = curr.random.next; curr = curr.next.next; }
  const dummy = {next: null}; let tail = dummy; curr = head;
  while (curr) {
    tail.next = curr.next; tail = tail.next;
    curr.next = curr.next.next; curr = curr.next;
  }
  return dummy.next;
}

Time: O(n) | Space: O(1) extra

Saved in this browser only. Private to you.

JavaScript