Copy List with Random Pointer Medium 0 attempts
LeetCode ↗

Copy List with Random Pointer

Medium Linked List LeetCode

Given a linked list where each node has an additional random pointer that could point to any node or null, create a deep copy of the list.

Example: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] → Deep copy with same structure

Sample Input
—
Sample Output
—
Constraints
  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • random is null or points to a node in the list
Topics
Linked List

Interleave + Separate

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

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