Katkat
Back

Deep-Copy a Linked List Whose Nodes Also Carry a Random Pointer

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Return a deep copy of a singly linked list in which every node also has a random pointer to any node or to nothing, so that the copy shares no node with the original. It tests mapping original nodes to copies, pointer wiring and constant-space alternatives.

Each node of a singly linked list has a value, a next pointer and a random pointer. The random pointer can point to any node of the list, including the node itself, or be None. Write a function that returns a deep copy of the list: a list of entirely new nodes with the same values, whose next and random pointers point to the corresponding new nodes and never to nodes of the original list.

class Node:
 def __init__(self, val, next=None, random=None):
 self.val = val
 self.next = next
 self.random = random

def copy_list(head: "Node | None") -> "Node | None":
 ...

original: A(7) -> B(13) -> C(11) -> None random: A -> None, B -> A, C -> C
copy: A'(7) -> B'(13) -> C'(11) -> None random: A' -> None, B' -> A', C' -> C'

Constraints and Clarifications

  • The list can be empty.
  • Several nodes can have their random pointers on the same node, and a random pointer can point backward or forward.
  • Values can repeat, so a node cannot be identified by its value.
  • The original list must be unchanged when the function returns.

Clarifying Questions

  • Is extra memory proportional to the length of the list acceptable, or should the copy use constant extra space besides the new nodes?
  • May the original list be modified temporarily during the copy, or do other threads read it at the same time?
  • How long can the list be, so that recursion depth becomes a concern?

Hints

Hint 1

Pointers to nodes not copied yet: When you copy a node, its random pointer may lead to a node further along the list. Think about how you could find the copy of any original node once that copy exists.

Hint 2

Prove the copy is deep: Think about what a test must check so that a copy which secretly points back into the original list fails.

Follow-up questions

  • Make the copy using constant extra space besides the new nodes.
  • The structure becomes a general graph in which each node has a list of neighbors. How does your approach change?
  • Other threads read the original list while you copy it. Which approach is still safe?