Entrevista técnica de código: Invertir nodos en grupos de k (Reverse Nodes in k-Group)

Planteamiento y contexto aplicable

Dada la cabeza head de una lista simplemente enlazada y un entero positivo k, invierte cada grupo completo de k nodos consecutivos in-place. Si quedan menos de k nodos al final, conserva su orden original. Reconecta los nodos en lugar de intercambiar los campos value.

Por ejemplo, 1 → 2 → 3 → 4 → 5 se convierte en 2 → 1 → 4 → 3 → 5 cuando k = 2, y se convierte en 3 → 2 → 1 → 4 → 5 cuando k = 3. Asume 1 ≤ k ≤ n ≤ 5000, que la entrada es acíclica y que el objetivo es un tiempo de O(n) con espacio extra de O(1).

Este problema es adecuado para entrevistas de código en roles de algoritmos, backend, infraestructura e ingeniería de software en general. La parte difícil no es la inversión básica de listas. Es demostrar que existe un grupo completo antes de la mutación, preservar la entrada al siguiente grupo, reconectar ambos límites y demostrar que ningún nodo se pierde ni queda atrapado en un ciclo.

Qué evalúa el entrevistador

La primera señal es si el candidato separa el descubrimiento de límites, la inversión de segmentos y la reconexión. Comenzar a invertir antes de saber si quedan k nodos hace que una cola incompleta sea difícil de restaurar sin almacenamiento adicional. Una solución sólida realiza una anticipación (lookahead) de solo lectura antes de modificar cualquier puntero.

La segunda señal es la propiedad clara de los punteros. groupPrev se ubica antes del grupo actual, kth es el último nodo de un grupo completo, groupNext es la entrada al siguiente segmento y la antigua cabeza del grupo se convierte en la nueva cola. Al final de cada iteración, el prefijo finalizado debe permanecer accesible y groupPrev.next debe ser el primer nodo no procesado.

La tercera señal es el uso de un invariante en lugar de código memorizado. Inicializar prev en groupNext hace que la antigua cabeza del grupo apunte al sufijo cuando se convierte en la cola. Una vez finalizada la inversión, solo es necesario conectar el prefijo anterior a kth; la conexión entre el grupo y el sufijo ya es correcta.

La cuarta señal es la disciplina en cuanto a complejidad. Cada nodo es visitado a lo sumo una vez por la anticipación de grupo completo y una vez por la inversión, por lo que el total es O(n), mientras que un número fijo de referencias proporciona un espacio extra de O(1). Una versión recursiva tiene el mismo límite de tiempo, pero consume espacio de pila proporcional al número de grupos.

Preguntas para aclarar antes de responder

• ¿Qué sucede con un grupo final menor a k? Aquí permanece sin cambios. Algunas variantes lo invierten, lo que

produce un resultado diferente.

• ¿Se pueden intercambiar los valores de los nodos? No. Los nodos pueden tener identidad, referencias externas o campos además del valor,

por lo que el intercambio de valores no es una inversión de nodos.

• ¿Qué valores de k son válidos? El planteamiento garantiza 1 ≤ k ≤ n. Una función reutilizable aún puede rechazar un

valor no entero o menor a uno.

• ¿Puede la entrada contener un ciclo? Este planteamiento indica que no. Si los ciclos fueran posibles, el contrato debería especificar si se

rechazan o se transforman; de lo contrario, la anticipación podría no terminar nunca.

• ¿El algoritmo debe ser in-place? Sí. Una pila es más simple cuando se permite un espacio de O(k), pero no cumple con este objetivo.
• ¿Se deben reutilizar los objetos nodo? Sí. Construir una nueva lista que solo copie valores viola el contrato.

Estructura de respuesta en 30 segundos

“Agregaré un nodo dummy antes de head y mantendré groupPrev inmediatamente antes del grupo actual. En cada iteración avanzo k pasos desde groupPrev para encontrar kth. Si eso falla, retorno de inmediato porque la cola no ha sido modificada. Tras guardar groupNext = kth.next, inicializo prev en groupNext e invierto el grupo actual puntero a puntero. Esto hace que la antigua cabeza del grupo sea la nueva cola que ya apunta a groupNext. Conecto groupPrev.next a kth y luego muevo groupPrev a la antigua cabeza del grupo. Cada nodo se visita una vez para la anticipación y una vez para la inversión, lo que resulta en un tiempo O(n) y un espacio extra O(1).”

Análisis detallado paso a paso

Comienza con un nodo dummy. La cabeza de la lista cambia cuando se invierte el primer grupo. El nodo dummy hace que conectar el prefijo a la nueva cabeza del grupo sea idéntico tanto para el primer grupo como para los posteriores, evitando un caso especial para la cabeza.

Cada iteración realiza primero una anticipación de grupo completo. Avanza exactamente k veces desde groupPrev para obtener kth. Si el recorrido llega a null, quedan menos de k nodos, por lo que se retorna dummy.next. La anticipación no ha escrito ningún puntero, motivo por el cual la cola incompleta permanece intacta automáticamente.

La implementación es:

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

function reverseKGroup(head, k) {
  if (!Number.isInteger(k) || k < 1) {
    throw new RangeError('k must be a positive integer')
  }

  const dummy = new ListNode(0, head)
  let groupPrev = dummy

  while (true) {
    let kth = groupPrev

    for (let step = 0; step < k; step += 1) {
      kth = kth.next
      if (kth === null) {
        return dummy.next
      }
    }

    const groupNext = kth.next
    let prev = groupNext
    let current = groupPrev.next

    while (current !== groupNext) {
      const nextNode = current.next
      current.next = prev
      prev = current
      current = nextNode
    }

    const oldGroupHead = groupPrev.next
    groupPrev.next = kth
    groupPrev = oldGroupHead
  }
}

Rastreo de 1 → 2 → 3 → 4 → 5 con k = 3. La anticipación encuentra kth = 3 y se guarda groupNext = 4. Se establece prev = 4 y luego se escriben 1.next = 4, 2.next = 1 y 3.next = 2. El nodo 3 es ahora la cabeza del grupo, mientras que el nodo 1 es la cola y ya alcanza al nodo 4. Se conecta el nodo dummy a 3 y se mueve groupPrev al nodo 1. La siguiente anticipación no puede encontrar tres nodos, por lo que retorna sin tocar 4 → 5.

El invariante del bucle consta de tres partes. Al entrar al bucle, el prefijo hasta groupPrev ha sido transformado correctamente en grupos completos; groupPrev.next es el primer nodo no procesado; y todos los nodos no procesados siguen siendo accesibles en el orden de entrada. Una anticipación fallida no realiza escrituras, por lo que el invariante demuestra directamente que la cola incompleta se conserva. Una anticipación exitosa limita la inversión a exactamente k nodos, mientras que groupNext preserva la entrada al sufijo. Tras la reconexión, el prefijo completado crece en un grupo y el invariante se restablece. Cada iteración exitosa consume k nodos nuevos, por lo que el algoritmo termina.

La anticipación y la inversión tocan cada nodo a lo sumo una vez a lo largo de todas las iteraciones. Por lo tanto, el trabajo total es como máximo de aproximadamente 2n visitas a nodos: O(n), no O(nk). El nodo dummy y la cantidad de punteros no crecen con la entrada, por lo que el espacio auxiliar es O(1).

Si se permite espacio extra, apilar un grupo en una estructura de pila (stack) y desapilarlo es más fácil de escribir, pero usa un espacio de O(k). Una solución recursiva puede confirmar un grupo completo, invertirlo y aplicar recursión sobre el sufijo, usando un espacio de pila de O(n / k). La versión iterativa es la recomendación correcta para un objetivo de espacio constante. Para una entrada pequeña donde la prioridad sea una primera versión rápida de revisar, el enfoque con pila puede ser una alternativa razonable expresada explícitamente.

Las pruebas deben ir más allá de comparar arreglos de valores. Guarda el conjunto de referencias de nodos originales, recorre el resultado y asegura que sea acíclico, tenga la misma cantidad de nodos y contenga exactamente las mismas referencias antes de verificar el orden. Cubre una entrada vacía por precaución, un nodo, k = 1, n = k, una longitud divisible exactamente, una cola incompleta, valores duplicados y el tamaño máximo. Los valores duplicados son especialmente útiles porque las pruebas basadas solo en valores no pueden demostrar que los objetos nodo fueron reutilizados.

Respuesta de muestra de alta calidad

“Primero confirmaría que los menos de k nodos finales permanezcan en su orden original y que los valores no puedan intercambiarse. Mi estado iterativo consiste en un nodo dummy más un número fijo de referencias. groupPrev siempre se sitúa inmediatamente antes del grupo actual. Avanzo k pasos desde él y, si kth no existe, retorno antes de modificar ningún puntero de la cola.

Para un grupo completo, guardo groupNext. Inicializo prev en groupNext y luego aplico la inversión estándar de tres punteros desde la antigua cabeza del grupo hasta llegar a groupNext. Esa inicialización es clave: cuando la antigua cabeza se convierte en la cola, su next ya alcanza al siguiente segmento. Tras la inversión, kth es la nueva cabeza. Conecto groupPrev.next a ella y muevo groupPrev a la antigua cabeza.

El invariante es que el prefijo procesado es correcto y está conectado, groupPrev.next es el primer nodo no procesado y el sufijo se mantiene en el orden de entrada. Una inversión completa expande el prefijo; un grupo incompleto no produce ninguna escritura, preservando la cola. Cada nodo se visita a lo sumo una vez para la anticipación y una vez para la inversión, por lo que el tiempo es O(n) y el espacio extra es O(1). Verificaría la identidad de los nodos y la aciclicidad, no únicamente la secuencia de valores.”

Errores comunes

• Invertir antes de confirmar un grupo completo → la cola incompleta queda modificada y resulta difícil de restaurar →

realizar primero una anticipación de solo lectura.

• Comenzar la inversión con prev = null → el grupo queda temporalmente desconectado del sufijo y es fácil dejarlo

aislado → comenzar con prev = groupNext.

• Conectar solo la nueva cabeza del grupo → la nueva cola podría no alcanzar al sufijo → **preservar groupNext y

verificar que la nueva cola apunte a él.**

• Mantener kth como el siguiente predecesor → el límite del siguiente grupo queda incorrecto → **mover groupPrev a la antigua

cabeza del grupo.**

• Intercambiar valores de nodos → se rompe la identidad de los nodos y la semántica de los campos asociados → modificar únicamente next.
• Afirmar que el espacio auxiliar recursivo es O(1) → la pila de llamadas crece con el conteo de grupos → **usar iteración para

un espacio extra constante.**

• Probar solo la secuencia de valores → nodos perdidos, copiados o en ciclo pueden pasar inadvertidos → **verificar también la identidad

de referencias, el conteo y la aciclicidad.**

• Multiplicar la anticipación por la inversión como O(nk) → los grupos son disjuntos entre iteraciones → **sumar el total de visitas

por nodo.**

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué pasa si el grupo final de menos de k nodos también debe invertirse?

Una anticipación fallida ya no puede retornar de inmediato. Puede contar el número real de nodos restantes e invertir ese segmento más corto, o el algoritmo puede calcular primero la longitud de la lista y usar min(k, remaining) como tamaño de grupo. La parte de terminación del invariante cambia, y un caso con n < k se vuelve obligatorio.

Pregunta de seguimiento 2: ¿Cómo invertirías grupos alternados?

Continúa anticipando por grupos completos de k nodos y mantén una bandera booleana. Un grupo a invertir utiliza la lógica original; un grupo omitido deja los punteros intactos y avanza groupPrev en k nodos. Aclara nuevamente la regla de la cola incompleta, ya que el resultado variará según se cuente como grupo omitido o invertido.

Pregunta de seguimiento 3: ¿Cómo puedes demostrar que el algoritmo no crea ciclos?

La demostración local utiliza dos límites: guardar groupNext, que está fuera del grupo actual, e invertir comenzando desde prev = groupNext hasta current === groupNext. Cada enlace reescrito apunta desde el nodo actual hacia un predecesor ya procesado o hacia la entrada del sufijo, nunca hacia la parte aún no procesada del grupo actual. Las pruebas también deberían ejecutar una comprobación de ciclos con punteros rápido/lento y verificar que el conteo de nodos recorridos coincida con el de entrada.

Pregunta de seguimiento 4: ¿Qué cambia para una lista con cien millones de nodos?

Los límites asintóticos siguen siendo los mismos, pero debe evitarse la recursión, no deben copiarse los nodos y el comportamiento frente a timeouts y cancelaciones cobra relevancia en una operación prolongada. Si la lista reside en almacenamiento externo o distribuida entre máquinas, la reconexión aleatoria y la visibilidad atómica dominan el problema. El algoritmo en memoria no puede trasladarse directamente; primero deben definirse la disposición de los datos, los límites de transacción y los puntos de control (checkpoints) recuperables.