Entrevista técnica de código: Copiar una lista enlazada con punteros aleatorios

Enunciado y contexto aplicable

Dada la cabeza de una lista simplemente enlazada acíclica, cada nodo contiene val, next y random. El puntero random es null o hace referencia a cualquier nodo alcanzable a través de la cadena next de la lista, incluido el propio nodo. Devuelve una copia profunda con exactamente un nodo nuevo por cada nodo original. Si el nodo original x apunta al nodo original y a través de cualquiera de los campos, la copia de x debe apuntar a través de ese campo a la copia de y.

Los valores de los nodos no son únicos, por lo que el valor no puede identificar a un nodo. La cadena next es finita, aunque las aristas random pueden apuntar hacia atrás, hacia adelante o formar ciclos. La lista devuelta no debe compartir ningún nodo con la entrada, y la entrada debe tener su estructura original cuando la función retorne.

Este es un problema de estructuras de datos e identidad de objetos. La respuesta base utiliza un mapa de cada objeto original a su copia. Una pregunta de seguimiento puede exigir espacio auxiliar constante; esa versión intercala temporalmente las copias con los originales y luego restaura la entrada. Los nodos de salida no cuentan como espacio auxiliar, pero aun así consumen O(n) de memoria total.

Qué evalúa el entrevistador

La primera señal es si el candidato define la copia profunda estructuralmente. La igualdad de valores no es suficiente. La respuesta necesita un mapeo uno a uno f de los nodos originales a los nodos nuevos de modo que se preserven ambas relaciones: la copia de x.next es f(x).next, y la copia de x.random es f(x).random.

La segunda señal es el manejo de una referencia antes de que su objetivo haya sido copiado. Una copia de valores en una sola pasada no puede conectar de forma segura una arista random hacia adelante. La solución directa separa la asignación de memoria de la conexión: crear primero todos los nodos de destino y luego conectar los punteros mediante el mapa de identidades.

La tercera señal es deducir la optimización de espacio en lugar de recitarla de memoria. Tras colocar cada copia inmediatamente después de su original, la copia de cualquier nodo original r es exactamente r.next. Ese invariante local reemplaza el mapa durante la asignación de los punteros aleatorios.

Por último, el entrevistador busca disciplina ante la mutación. El método de intercalado está incompleto hasta que restaura cada puntero next original, extrae una cadena copiada válida y explica cuándo es inaceptable mutar temporalmente la entrada.

Preguntas para aclarar antes de responder

• ¿Puede random apuntar fuera de la lista? Este enunciado indica que no. Si los nodos externos pertenecen al clon, el alcance se convierte en una copia general de grafos alcanzables; si no pertenecen, el contrato de salida debe indicar si se deben retener, limpiar o rechazar esas referencias.
• ¿Puede la cadena next contener un ciclo? No. Si pudiera, un bucle que solo siga next nunca terminaría sin un conjunto de visitados, y el problema se abordaría mejor como la clonación de un grafo.
• ¿Puede el algoritmo mutar la entrada temporalmente? La solución con mapa no lo hace. La solución de intercalado sí lo hace y solo es adecuada cuando la función tiene acceso mutable exclusivo y restaura la lista antes de retornar.
• ¿Qué cuenta como espacio adicional? Los nodos copiados son la salida requerida. El mapa cuesta O(n) de espacio auxiliar; el intercalado utiliza O(1) punteros auxiliares además de la salida O(n).
• ¿Los valores son únicos? No. Un mapa con claves basadas en valores fusionaría nodos distintos y corrompería las referencias; las claves deben ser las identidades de los nodos.
• ¿Qué debe devolver una entrada vacía? Devolver null.

Estructura de respuesta en 30 segundos

“Primero lo resolveré con un mapa de identidades de original a copia. Una pasada asigna cada nodo copiado y una segunda pasada asigna los punteros copiados next y random buscando los objetivos originales correspondientes. Eso toma tiempo O(n) y espacio auxiliar O(n). Si el entrevistador requiere espacio auxiliar constante y se permite la mutación temporal, puedo insertar cada copia inmediatamente después de su original. Entonces, la copia del objetivo aleatorio de un original es su nodo siguiente. Una tercera pasada separa las cadenas mientras restaura la entrada. Ambos métodos son lineales; la versión por intercalado utiliza espacio auxiliar O(1), excluyendo la salida requerida.”

Respuesta detallada paso a paso

Una copia superficial falla porque reutiliza las referencias originales. Copiar únicamente los valores también falla: dos nodos diferentes pueden tener el mismo valor, y random puede apuntar a un nodo que aún no ha aparecido en el recorrido. Seguir random recursivamente no es un atajo porque las aristas aleatorias pueden formar ciclos.

La línea base más segura crea una biyección explícitamente. La primera pasada asigna un nuevo objeto por cada original. La segunda pasada traduce ambas aristas salientes a través de ese mapa. Incluir null -> null en la búsqueda es opcional; las comprobaciones explícitas de nulo suelen ser más claras en una entrevista.

class RandomListNode {
  val: number
  next: RandomListNode | null
  random: RandomListNode | null

  constructor(
    val: number,
    next: RandomListNode | null = null,
    random: RandomListNode | null = null,
  ) {
    this.val = val
    this.next = next
    this.random = random
  }
}

function copyWithMap(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  const copies = new Map<RandomListNode, RandomListNode>()

  let current: RandomListNode | null = head
  while (current !== null) {
    copies.set(current, new RandomListNode(current.val))
    current = current.next
  }

  current = head
  while (current !== null) {
    const copy = copies.get(current)!
    copy.next = current.next === null ? null : copies.get(current.next)!
    copy.random = current.random === null ? null : copies.get(current.random)!
    current = current.next
  }

  return copies.get(head)!
}

El invariante tras la primera pasada es simple: cada original visitado a través de next tiene exactamente una entrada distinta en el mapa, y ningún puntero copiado tiene que apuntar a un nodo sin asignar. Durante la segunda pasada, traducir una arista de x a y en una arista de f(x) a f(y) preserva el grafo. El método realiza dos pasadas lineales, por lo que el tiempo es O(n) y el espacio auxiliar es O(n).

Para eliminar el mapa, almacena temporalmente la misma correspondencia en la topología de la lista. Transforma esta cadena:

A -> B -> C -> null

en esta cadena intercalada:

A -> A' -> B -> B' -> C -> C' -> null

Ahora A' es A.next, y si A.random apunta a C, entonces el objetivo correcto para A'.random es A.random.next, que es C'. Esto funciona para aristas hacia adelante, hacia atrás, autorreferencias y objetivos repetidos porque depende de la posición del objeto, no de los valores.

function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  let current: RandomListNode | null = head
  while (current !== null) {
    const copy: RandomListNode = new RandomListNode(current.val, current.next)
    current.next = copy
    current = copy.next
  }

  current = head
  while (current !== null) {
    const copy: RandomListNode = current.next!
    copy.random = current.random === null ? null : current.random.next
    current = copy.next
  }

  const copiedHead = head.next
  current = head

  while (current !== null) {
    const copy: RandomListNode = current.next!
    const nextOriginal: RandomListNode | null = copy.next

    current.next = nextOriginal
    copy.next = nextOriginal === null ? null : nextOriginal.next
    current = nextOriginal
  }

  return copiedHead
}

La corrección se deduce de tres invariantes de pasada. Tras la pasada uno, cada original está seguido inmediatamente por su copia única. Durante la pasada dos, cada arista aleatoria copiada va a la copia que está inmediatamente después del objetivo original. Durante la pasada tres, cada iteración restaura una arista original y conecta una arista copiada al siguiente nodo copiado. Cuando el bucle termina, la cadena original queda restaurada y cada puntero alcanzable desde la cabeza copiada apunta únicamente a nodos copiados.

El método de intercalado realiza tres pasadas lineales, por lo que el tiempo sigue siendo O(n). Almacena solo una cantidad fija de punteros de trabajo, por lo que el espacio auxiliar es O(1), excluyendo los n nodos nuevos requeridos. No es automáticamente la mejor opción para producción: durante las dos primeras pasadas, otros lectores ven una entrada con aspecto corrupto, y una excepción antes de la separación puede dejar la lista intercalada. La solución con mapa es más fácil de auditar y admite entradas inmutables o compartidas.

Prueba la estructura, la identidad y la restauración por separado. Cubre una lista vacía; un nodo con random = null; un nodo cuyo puntero aleatorio apunta a sí mismo; valores duplicados; dos nodos cuyos punteros aleatorios se cruzan; aristas aleatorias hacia adelante y hacia atrás; y múltiples nodos apuntando al mismo objetivo. Tras clonar, muta un valor copiado y verifica que el original no cambie. Recorre el original nuevamente para verificar que su cadena next fue restaurada, y valida con aserciones que ningún puntero copiado next o random pertenezca al conjunto de nodos originales.

Respuesta de muestra de alta calidad

“La parte importante es preservar la identidad de los nodos, no solo los valores. Los valores pueden repetirse y una arista aleatoria puede apuntar hacia adelante o formar un ciclo, por lo que no usaría claves basadas en valores ni seguiría recursivamente punteros aleatorios sin un estado de visitados.

Mi solución base consiste en dos pasadas con un mapa de identidades. La primera pasada recorre la cadena acíclica next y asigna una copia por cada original. La segunda pasada traduce ambos punteros mediante el mapa. Eso establece directamente una correspondencia uno a uno, toma tiempo lineal y utiliza espacio auxiliar lineal. Es la versión que elegiría cuando la entrada es inmutable, compartida, o cuando prima la implementación auditable más simple.

Si el espacio auxiliar constante es un requisito estricto y se me permite mutar temporalmente, insertaría cada copia después de su original. Eso hace que el mapeo sea implícito: la copia de cualquier objetivo original es target.next. Luego asigno cada puntero aleatorio copiado y separo la cadena alternada. La pasada de separación debe actualizar ambas cadenas, de modo que el original quede exactamente restaurado y la copia no contenga referencias hacia él.

Demostraría los tres invariantes después del entrelazado, la asignación aleatoria y la separación, y luego probaría punteros random hacia sí mismos, valores duplicados, aristas aleatorias cruzadas, entrada vacía e independencia posterior a la copia. Ambas versiones toman tiempo O(n); la segunda usa espacio auxiliar O(1) pero sigue asignando la salida de O(n) y no es segura con lectores concurrentes.”

Errores comunes

• Usar el valor del nodo como clave del mapa -> los valores duplicados colapsan identidades distintas -> usar como clave el objeto del nodo original.
• Copiar random directamente -> la salida sigue apuntando hacia la entrada -> traducir cada objetivo no nulo a su nodo copiado.
• Asignar y conectar en una sola pasada ingenua hacia adelante -> un objetivo aleatorio hacia adelante podría no existir todavía -> asignar todos los nodos primero o crear copias faltantes a través de un mapa de identidades completo.
• Seguir punteros aleatorios recursivamente sin estado de visitados -> los ciclos aleatorios provocan recursión infinita o nodos duplicados -> usar la cadena next finita para este contrato o un mapa de visitados para grafos generales.
• Llamar al método de intercalado espacio O(1) sin matizar -> la lista devuelta aún contiene n nodos nuevos -> indicar espacio auxiliar O(1) excluyendo la salida requerida.
• Asignar copy.random = current.random.next sin comprobación de nulo -> un puntero aleatorio nulo causa un fallo -> preservar el valor null explícitamente.
• Desconectar únicamente la cadena copiada -> los nodos originales permanecen enlazados a través de las copias -> restaurar el original y construir la cadena copiada en la misma pasada de separación.
• Usar intercalado en entradas compartidas -> los lectores concurrentes observan las copias insertadas -> usar la solución con mapa a menos que se garantice una mutación temporal exclusiva.
• Probar únicamente valores -> una copia superficial puede pasar comparaciones de valor -> validar identidades distintas, aristas traducidas, restauración del original e independencia de mutación.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué pasa si la entrada nunca debe modificarse, ni siquiera temporalmente?

Utiliza la solución de mapa de identidades. Ofrece tiempo O(n) y espacio auxiliar O(n) mientras deja la fuente intacta durante toda la ejecución. Copiar en arreglos por índice de recorrido también consume espacio O(n) y aún necesita un mapeo de identidad a índice a menos que la entrada ya exponga índices estables. La optimización por intercalado viola el contrato más estricto de inmutabilidad incluso si restaura la lista más adelante.

Pregunta de seguimiento 2: ¿Qué pasa si random puede apuntar a un nodo fuera de la cadena next?

Primero define la propiedad del clon. Si los nodos externos también deben copiarse, la entrada es un grafo cuyas aristas salientes son next y random; usa DFS o BFS con un mapa de identidades y clona cada nodo alcanzable una sola vez. Si los nodos externos se comparten intencionalmente, el contrato debe permitir referencias externas retenidas. El intercalado no puede descubrir ni posicionar copias para objetivos externos arbitrarios.

Pregunta de seguimiento 3: ¿Qué pasa si los punteros next pueden formar un ciclo?

Un recorrido simple con while current !== null no terminará. Trata ambos campos como aristas de un grafo y mantén un mapa de identidades visitadas. Crea la copia de un nodo la primera vez que sea descubierto y luego encola los vecinos no vistos. El tiempo y el espacio pasan a ser O(V + E) para el grafo alcanzable, con a lo sumo dos aristas salientes por nodo en este modelo.

Pregunta de seguimiento 4: ¿Cómo verificarías que la copia sea realmente profunda?

Construye un mapa únicamente dentro de la prueba desde las identidades originales a las identidades copiadas mientras recorres ambas cadenas next. Valida longitudes y valores iguales, identidades de nodo diferentes y, para cada arista, que el objetivo copiado coincida con el objetivo original mapeado. También verifica que ningún puntero de salida esté en el conjunto de nodos originales. Finalmente, muta valores y punteros en la copia y confirma que la fuente permanezca sin cambios; para el intercalado, compara las identidades de punteros de la fuente antes y después de la llamada.

Pregunta de seguimiento 5: ¿Qué solución enviarías a producción?

Por defecto elegiría la versión con mapa de dos pasadas porque su invariante es explícito y nunca expone una entrada modificada transitoriamente. Elegiría el intercalado únicamente cuando la memoria auxiliar sea una restricción medida, la lista sea de propiedad exclusiva durante toda la llamada y el manejo de fallos pueda garantizar la restauración. La mejora asintótica de espacio no elimina los costos de concurrencia, seguridad frente a excepciones y mantenibilidad.